#include<iostream>
using namespace std;
int main()
{
    long T,yu;
    long feng;
   while(cin>>T&&T)
   {
    yu=T%4018;
    if(yu%2==0)    
        feng=((((yu*yu)/4)%2009)*((2*yu+3)%2009));
    else
        feng=((((yu+1)*(yu+1)/4)%2009)*((2*yu-1)%2009));
    printf("%ld\n",feng%2009);
   }
return 0;
}