#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
const int mod=1e9+1;
int n,vst[20],vis[100010],a[20][20],f[20][1<<11];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
bool judge(int x){return (x&(x<<1))==0;}
int solve(int x){
	a[1][1]=x;  memset(vst,0,sizeof(vst));
	for(int i=2;i<=18;++i) {a[i][1]=a[i-1][1]*2; if(a[i][1]>n) a[i][1]=n+1;}
	for(int i=1;i<=18;++i)for(int j=2;j<=11;++j){
		a[i][j]=a[i][j-1]*3;
		if(a[i][j]>n)  a[i][j]=n+1;
	}
	for(int i=1;i<=18;++i)for(int j=1;j<=11;++j)if(a[i][j]<=n)
		vst[i]|=(1<<(j-1)),vis[a[i][j]]=1;
	memset(f,0,sizeof(f)); f[0][0]=1;
	for(int i=1;i<=18;++i)for(int j=0;j<=vst[i];++j)if(judge(j)){
		for(int k=0;k<=vst[i-1];++k)if(judge(k)&&((k&j)==0)){
			f[i][j]+=f[i-1][k];  f[i][j]%=mod;
		}
	}
	return f[18][0];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  ll ans=1;
	for(int i=1;i<=n;++i)if(!vis[i])ans=ans*solve(i)%mod;
	printf("%lld\n",ans);
	return 0;
}