#include <iostream>

#include <string.h>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

typedef long long ll;

const int P = 1e9+1;

const int N = 1e5+10;

int n, vis[N];

int a[30], s[1<<11];

int dp[2][1<<11];

int calc(int x) {

	memset(dp,0,sizeof dp);

	memset(a,0,sizeof a);

	int dx = 0, dy = 0;

	for (int i=1,t=x; t<=n; t*=2,++i) {

		for (int j=1,tt=t; tt<=n; tt*=3,++j) {

			(a[i]<<=1)|=1, vis[tt] = 1;

			dx = max(dx, i);

			dy = max(dy, j);

		}

	}

	int mx = (1<<dy)-1, cnt = 0;

	REP(i,0,mx) if (!(i&i<<1)) s[++cnt] = i;

	int cur = 0;

	dp[cur][1] = 1;

	REP(i,1,dx) {

		cur ^= 1;

		memset(dp[cur],0,sizeof dp[cur]);

		REP(j,1,cnt) if (dp[!cur][j]) {

			REP(k,1,cnt) if (!(s[j]&s[k])&&(s[k]|a[i])==a[i]) {

				dp[cur][k]=(dp[cur][k]+dp[!cur][j])%P;

			}

		}

	}

	int ans = 0;

	REP(i,1,cnt) ans=(ans+dp[cur][i])%P;

	return ans;

}

int main() {

	scanf("%d", &n);

	int ans = 1;

	REP(i,1,n) if (!vis[i]) ans=(ll)ans*calc(i)%P;

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

}