1 #include <bits/stdc++.h>
 2 #define mod 1000000001
 3 using namespace std;
 4 int n,vis[100010],ans,num[23];
 5 int mps[20][20],tt[100000],x;
 6 int f[23][7000];
 7 bool check(int x)
 8 {
 9     for(int i=1;i<=18;i++)
10         if((x>>(i-1))&(x>>i)) return 0;
11     return 1;
12 }
13 void print(int x)
14 {
15     while(x) printf("%d",x&1),x/=2;
16     printf("\n");
17 }
18 void add(int &x,int y)
19 {
20     x+=y; if(x>=mod) x-=mod;
21 }
22 int solve()
23 {
24     for(int i=1;i<=tt[0]&&tt[i]<=(1<<num[1])-1;i++)
25         f[1][i]=1;
26     for(int i=2;i<=x;i++)
27         for(int j=1;j<=tt[0]&&tt[j]<=(1<<num[i])-1;j++)
28         {
29             f[i][j]=0;
30             for(int k=1;k<=tt[0]&&tt[k]<=(1<<num[i-1])-1;k++)
31             if(!(tt[j]&tt[k])) add(f[i][j],f[i-1][k]);
32         }
33     int tmp=0;
34     for(int i=1;i<=tt[0]&&tt[i]<=(1<<num[x])-1;i++)
35         add(tmp,f[x][i]);
36     long long gg=ans;
37     gg*=tmp; gg%=mod;
38     ans=gg;
39 }
40 int main()
41 {
42     scanf("%d",&n);ans=1;
43     for(int i=0;i<(1<<18);i++)
44         if(check(i)) tt[++tt[0]]=i;
45     for(int i=1;i<=n;i++)
46     {
47         if(vis[i]) continue;mps[1][1]=i; x=1;
48         vis[i]=1;num[1]=1;
49         for(int j=2;mps[1][j-1]*2<=n;j++)
50             vis[mps[1][j]=mps[1][j-1]*2]=1,num[1]=max(num[1],j);
51         for(int j=2;mps[j-1][1]*3<=n;j++)
52         {
53             vis[mps[j][1]=mps[j-1][1]*3]=1;num[j]=1;
54             for(int t=2;mps[j][t-1]*2<=n;t++)
55                 vis[mps[j][t]=mps[j][t-1]*2]=1,num[j]=max(num[j],t);
56             x++;
57         }
58     /*    for(int i=1;i<=x;i++)
59         {
60             for(int j=1;j<=num[i];j++)
61                 printf("%d ",mps[i][j]);
62             printf("\n");
63         }*/
64         solve(); 
65     }
66     cout<<ans<<endl;
67     return 0;
68 }