1 #include <cstdio> 2 #include <cstring> 3 #include <map> 4 #define ll long long 5 #include <algorithm> 6 using namespace std; 7  8 ll n; 9 map<ll,ll>q;10 11 ll quickmod(ll a,ll b,ll m)12 {13     ll ans = 1;14     ll c=a%m;15     while(b)16     {17         if(b&1)18         {19             ans = (ans*c)%m;20             b--;21         }22         b/=2;23         c = c*c%m;24     }25     return ans;26 }27 28 ll Get_num(int n)29 {30     if(q[n]!=0)31     {32         return q[n];33     }34     else35     {36         ll ans=quickmod(2,n,2008);37         ans-=2;38         ans%=2008;39         for(int i=2; i*i<=n; i++)40         {41             if(n%i!=0) continue;42             if(i*i==n)43             {44                 ans-=Get_num(i);45                 ans%=2008;46             }47             else48             {49                 ans-=Get_num(i);50                 ans-=Get_num(n/i);51                 ans%=2008;52             }53         }54         ans=(ans+2008)%2008;55         q[n]=ans;56         return ans;57     }58 }59 int main()60 {61     q[1]=2;62     while(scanf("%lld",&n)!=EOF)63     {64         printf("%lld\n",Get_num(n));65     }66     return 0;67 }