#include<stdio.h>
#define int long long

int n,p[14000005]={1},dp[16][16385];
int ny[14000005];
const int mod=1e9+7;

int max(int a,int b){
	if(a>b) return a;
	return b;
}

int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int inv(int x){
	return qpow(x,mod-2);
}

int c(int n,int m){
	if(m>n) return 0;
	return (p[n]*ny[m]%mod)*ny[n-m]%mod;
}

void solve(){
	scanf("%lld",&n);
	dp[0][1]=1;
	for(int i=1;i<=14000000;i++) p[i]=p[i-1]*i%mod;
	ny[14000000]=qpow(p[14000000],mod-2);
	for(int i=14000000-1;i>=0;i--){
		ny[i]=(ny[i+1]*(i+1))%mod;
	}
	for(int i=1;i<=15;i++){
		int sheng=n-qpow(3,i-1),xuan=qpow(3,i)-qpow(3,i-1);
		if(sheng<=xuan){
			for(int j=1;j<=(1<<(i-1));j++){
				dp[i][0]=(dp[i][0]+dp[i-1][j])%mod;
			}
			break;
		}
		int all=inv(c(sheng,xuan));
		for(int j=0;j<=(1<<i);j++){
			for(int k=max(1ll,(j+1)>>1);k<=(1<<(i-1));k++){
				int gan=2*k-j;
				dp[i][j]=(dp[i][j]+dp[i-1][k]*c(2*k,gan)%mod*c(sheng-2*k,xuan-gan)%mod*all)%mod;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=15;i++) ans=(ans+dp[i][0]*i)%mod;
	printf("%lld",ans);
}

signed main(){
	int T=1;/*
	cin>>T;//*/
	while(T--) solve();
	return 0;
}

Compiler Output Limit Exceeded