#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=14e6+6;

ll n;
ll jie[N],inv[N],top,pow3[20];
ll dp[2][N];

bool v[N];
vector<int>id;

inline void add(ll &x,ll y){
	x+=y-(x+y>=mod?mod:0);
}

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

void init(ll lim){
	jie[0]=1;
	for(ll i=1;i<=lim;i++)jie[i]=1ll*jie[i-1]*i%mod;
	inv[lim]=ksm(jie[lim],mod-2);
	for(ll i=lim;i>=1;i--)inv[i-1]=1ll*inv[i]*i%mod;
	pow3[0]=1;
	while(pow3[top]<n)pow3[++top]=pow3[top-1]*3;
}

ll C(ll n,ll m){
	return 1ll*jie[n]*inv[m]%mod*inv[n-m]%mod;
}

ll invC(ll n,ll m){
	return 1ll*inv[n]*jie[m]%mod*jie[n-m]%mod;
}

int main(){
	scanf("%lld",&n);
	init(n);
	ll ans=0;
	dp[0][1]=1;
	for(ll i=1;i<=top;i++){
		ll p=i&1,q=p^1;
		ll lim=min(n-pow3[i-1],2*pow3[i-1]);
		ll inv_num=invC(n-pow3[i-1],lim);
		for(ll j=1;j<=(1<<i-1)&&j<=n&&j+pow3[i-1]<=n;j++){
			ll infected=min(n-pow3[i-1]-j,j);
			for(ll k=0;k<=j+infected&&k<=lim;k++){
				ll temp=1ll*C(j+infected,k)*C(n-pow3[i-1]-j-infected,lim-k)%mod;
				temp=(1ll*temp*inv_num)%mod;
				temp=(1ll*temp*dp[q][j])%mod;
				if(!v[j+infected-k]){
					dp[p][j+infected-k]=0;
					v[j+infected-k]=1;
					id.push_back(j+infected-k);
				}
				add(dp[p][j+infected-k],temp);
			}
		}
		for(auto x:id)v[x]=0;
		id.clear();
		add(ans,1ll*dp[p][0]*i%mod);
		//printf("%d:%d\n",i,3ll*dp[p][0]%mod);
	}
	printf("%lld\n",ans);
	//printf("%d\n",5ll*ksm(3,mod-2)%mod);
}