#include<bits/stdc++.h>
using namespace std;
unsigned long long n,p,q,cnt[4111],f[21],dp[21][21][4111];
bool a[4111],w[111111];
bool C(unsigned long long d,unsigned long long b){
	return (f[d]|b)==f[d];
}
void ContT(unsigned long long input){
	unsigned long long quotient = input;
    unsigned long long remainder = 0;
    unsigned long long result = 0;
    unsigned long long time = 1;
    
    while (quotient != 0 ) {
        remainder = quotient % 2;       //求余数
        result += remainder * time;    //将余数化为一个具体的值
        quotient = quotient / 2;      //求商J
        time *= 10;
    }
  printf("%03d\n",result);
}
unsigned long long OPT(unsigned long long PO){
	memset(dp,0,sizeof dp);
	q=0,p=0;
	for(unsigned long long i=PO;i<=n;i*=2){
		//dp[i][0][0]=1;
		p++;
		f[p]=0;
		for(unsigned long long j=i;j<=n;j*=3){
			w[j]=1;
			//cout<<j<<" ";
			f[p]=f[p]*2+1;
		}
		//cout<<endl<<f[p]<<endl;
		cout<<p<<":";
		ContT(f[p]);
	}
	for(unsigned long long i=1;i<=n;i*=3){
		q++;
	}
	dp[0][0][0]=1;
	for(unsigned long long i=1;i<=p;i++){
		cout<<"i:"<<i<<endl;
		for(unsigned long long A=0;A<=(1<<q)-1;A++){
			if(a[A]&&C(i,A)){
				cout<<"  A:";
				ContT(A);
				for(unsigned long long B=0;B<=(1<<q)-1;B++){
					if(a[B]&&C(i-1,B)&&(!(A&B))){
						cout<<"    B:";
						ContT(B);
						for(unsigned long long l=cnt[A]+cnt[B];l<=i*q;l++){
							unsigned long long OLD=dp[i][l][A];
							dp[i][l][A]+=dp[i-1][l-cnt[A]][B];
							cout<<"      ans(l="<<l<<"):"<<dp[i][l][A]<<"<--"<<dp[i-1][l-cnt[A]][B]<<"("<<OLD<<")"<<"{["<<i<<","<<l<<"],["<<i-1<<","<<l-cnt[A]<<"]}"<<endl;
							dp[i][l][A]%=1000000001;
						}
					}
				}
			}
		}
	}
	unsigned long long ans=0;
	for(unsigned long long i=0;i<=(1<<q)-1;i++){
		if(a[i]){
			for(unsigned long long j=cnt[i];j<=p*q;j++){
				ans+=dp[p][j][i];
				ans%=1000000001;
			}
		}
	}
	cout<<PO<<" "<<ans<<endl;
	return ans;
}
int main(){
	cin>>n;
	unsigned long long ans=1;
	q=log(n)/log(3)+1;
	for(unsigned long long i=0;i<=(1<<q)-1;i++){
		for(unsigned long long j=0;j<q;j++){
			if(i&(1<<j)){
				cnt[i]++;
			}
		}
		a[i]=!((i<<1)&i);
	}
	for(unsigned long long i=1;i<=n;i++){
		if(!w[i]){
			ans*=OPT(i);
			ans%=1000000001;
		}
	}
	cout<<ans;
}