#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <iostream>

using namespace std;

#define N 25

#define M 1<<11

#define mod 1000000001

int f[N][M],a[N][N],b[N],K,n,m,vis[1000005];

long long ans=1;

int calc(int t)

{

	memset(b,0,sizeof(b));

	a[1][1]=t;

	for(int i=2;i<=18;i++)

	{

		a[i][1]=a[i-1][1]<<1;

		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)

			{

				b[i]+=(1<<(j-1));

				vis[a[i][j]]=1;

			}

		}

	}

	for(int i=0;i<=18;i++)

	{

		for(int S=0;S<=b[i];S++)

		{

			f[i][S]=0;

		}

	}

	f[0][0]=1;

	for(int i=1;i<=18;i++)

	{

		for(int S=0;S<=b[i-1];S++)

		{

			if(!f[i-1][S])continue;

			for(int s=0;s<=b[i];s++)

			{

				if((S&s)||(s&(s<<1)))continue;

				f[i][s]=(f[i][s]+f[i-1][S])%mod;

			}

		}

	}

	return f[18][0];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		if(!vis[i])

		{

			ans=(ans*calc(i))%mod;

		}

	}

	printf("%lld\n",ans);

	return 0;

}