1 /* 2802 */ 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5  6 #define MAXN 4018 7 #define MOD  2009 8  9 __int64 a[MAXN+1];10 11 void init() {12     __int64 tmp;13     int i, j, k;14     bool flag;15     16     a[0]=0, a[1] = 1, a[2] = 7;17     for (i=3; i<=MAXN; ++i) {18         tmp = i%MOD;19         a[i] = (tmp*tmp*tmp - a[i-1]+MOD)%MOD;20     }21 }22 23 int main() {24     int n;25     26     #ifndef ONLINE_JUDGE27         freopen("data.in", "r", stdin);28         freopen("data.out", "w", stdout);29     #endif30     31     init();32     33     while (scanf("%d", &n)!=EOF && n) {34         n %= MAXN;35         printf("%I64d\n", a[n]);36     }37     38     return 0;39 }