1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <math.h>
 5 using namespace std;
 6 #define mod 2008
 7 #define ll int
 8 int a[100000001]={0};
 9 ll exp_mod(ll a,ll n)//(a^n)%b
10 {
11     ll t;
12     if(n==0)
13         return 1;
14     t=exp_mod(a,n/2);
15     t=t*t%mod;
16     if((n&1)==1)
17         t=t*a%mod;
18     return t;
19 }
20 int fun(int n)
21 {
22     int i,j;
23     if(a[n])
24     {
25         return a[n];
26     }
27     int an=exp_mod(2,n)-2;
28     for(i=2; i<=sqrt(n) ;i++)
29         if(n%i==0)
30         {
31             an-=fun(i);
32             if(i!=n/i)
33             an-=fun(n/i);
34             an%=mod;
35         }
36     return (an+mod)%mod;
37 }
38 int main()
39 {
40     int n;
41     a[1]=a[2]=2,a[3]=6,a[4]=12;
42     while(~scanf("%d",&n))
43     {
44         printf("%d\n",fun(n));
45     }
46 }