#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;

const int mo=1e9+7, N=2e7+5;
int dp[17][400005];
int ksm(int a,int b=mo-2)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mo;
        a=a*a%mo; b>>=1;
    }
    return res;
}
int fac[N], inv[N];
void init()
{
    fac[0]=inv[0]=1;
    int m=2e7;
    for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mo;
    inv[m]=ksm(fac[m]);
    for(int i=m-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mo;
}
int C(int n,int m)
{
    if(m>n || m<0 || n<0) return 0;
    return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
void solve(){
    init();
    int n; cin>>n;
    int cnt=0, t=1;
    while(t<n) t*=3, cnt++;
    dp[0][1]=1;
    // dp[1][2]=
    int mxj=1,mxc=1;
    for(int i=1;i<cnt;i++)
    {
        mxj*=2;
        for(int j=0;j<=mxj;j++)
        {
            int sum=n-mxc, c=2*mxc;
            int tmp=ksm(C(sum,c));
            for(int k=1;k<=mxj/2;k++)
            {
                // cout<<i<<' '<<j<<' '<<k<<" ???\n";
                dp[i][j]+=dp[i-1][k]*C(2*k,j)%mo*C(sum-2*k,c-(2*k-j))%mo*tmp%mo;
                dp[i][j]%=mo;
            }
            // cout<<i<<' '<<j<<' '<<dp[i][j]<<"\n";
        }
        mxc*=3;
    } 
    int ans=0;
    // cout<<dp[2][0]<<"\n";
    // for(int i=1;i<=1000;i++) if(i*ksm(36)%mo==dp[2][0]) cout<<i<<"\n";
    // cout<<dp[2][0]<<' '<<35*ksm(36)%mo<<"\n";
    for(int i=1;i<cnt;i++) (ans+=i*dp[i][0]%mo)%=mo;
    // cout<<ans<<"\n";
    // cout<<39*ksm(36)%mo<<"\n";
    for(int i=1;i<=ksm(2,cnt+1);i++) (ans+=cnt*dp[cnt-1][i]%mo)%=mo;
    cout<<ans<<'\n';
    // for(int i=1;i<=500;i++) if(i*ksm(36)%mo==ans) cout<<i<<"\n";
    // cout<<ans<<"\n";
    // cout<<87*ksm(36)%mo<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}