#include <cstdio>
const int M = 100005;
const int MOD = 1e9+1;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,ans,vis[M],lim[M];
int a[12][20],dp[12][1<<18],g[1<<18];
void build(int x)
{
	for(int i=1;i<=11;i++)
	{
		if(i==1) a[1][1]=x;
		else a[i][1]=a[i-1][1]*3;
		if(a[i][1]>n) break;
		m=i;vis[a[i][1]]=1;int cnt=1;
		for(int j=2;j<=18;j++)
		{
			a[i][j]=a[i][j-1]*2;
			if(a[i][j]>n) break;
			vis[a[i][j]]=1;cnt=j;
		}
		lim[i]=1<<cnt;
	}
}
int ask(int x)
{
	int res=0;
	for(int i=0;i<lim[1];i++)
		dp[1][i]=g[i];
	for(int i=2;i<=m;i++) for(int j=0;j<lim[i];j++)
	{
		if(!g[j]) continue;dp[i][j]=0;
		for(int k=0;k<lim[i-1];k++)
			if(g[k] && (k&j)==0)
				dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
	}
	for(int i=0;i<lim[m];i++)
		res=(res+dp[m][i])%MOD;
	return res;
}
signed main()
{
	n=read();ans=1;
	for(int i=0;i<(1<<18);i++)
		g[i]=!((i<<1)&(i));
	for(int i=1;i<=n;i++) if(!vis[i])
		build(i),ans=1ll*ans*ask(i)%MOD;
	printf("%d\n",ans);
}