/* 2802 */

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #define MAXN 4018

 #define MOD  2009

 __int64 a[MAXN+];

 void init() {

     __int64 tmp;

     int i, j, k;

     bool flag;

     a[]=, a[] = , a[] = ;

     for (i=; i<=MAXN; ++i) {

         tmp = i%MOD;

         a[i] = (tmp*tmp*tmp - a[i-]+MOD)%MOD;

     }

 }

 int main() {

     int n;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     init();

     while (scanf("%d", &n)!=EOF && n) {

         n %= MAXN;

         printf("%I64d\n", a[n]);

     }

     return ;

 }