#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod = 1e9+7,N = 15e6+10;
int in[N],inv[N];
int dp[20][50005];
int qmi(int a,int k)
{
    int res = 1;
    while(k)
    {
        if(k&1) res = res*a%mod;
        a = a*a%mod;
        k>>=1;
    }
    return res;
}

int get(int n)
{
    int l = 1, r = 400;
    while(l<r)
    {
        int mid = l+r>>1;
        if(qmi(3,mid)>=n)
        {
            r = mid;
        }
        else l = mid+1;
    }
    return l;
}
void init()
{
    in[0] = inv[0] = 1;
    for(int i=1;i<N;i++)    in[i] = in[i-1] * i % mod;
    inv[N-1] = qmi(in[N-1],mod-2);
    for(int i=N-2;i>=1;i--)
    {
        inv[i] = inv[i+1] * (i+1) % mod;
    }
}

int C(int a,int b)
{
    if(b>a || a<0 || b<0) return 0;
    return in[a] * inv[b] % mod * inv[a-b] % mod;
}
int inC(int a,int b)
{
    if(b>a || b<0 || a<0) return 0;
    return inv[a] * in[b] % mod * in[a-b]%mod;
}

signed main()
{
    init();
    int n;  cin>>n;
    dp[0][1] = 1; //前i天A集合中元素个数为j的概率
    int da = get(n); // 最多执行几天
    int inft = qmi(2,da-1);
    for(int i=0;i<da;i++)
    {
        for(int j=1;j<=inft;j++) //枚举A集合的元素个数
        {
            if(dp[i][j]==0) break;
            int vac = qmi(3,i); // 第i天的接种总人数
            int infd = min(n-vac,2*j); //第i天被感染的总人数。
            int cure = min(n-vac,2*vac); // 第i天被接种人数
            for(int k=0;k<=min(infd,n-vac-cure);k++)
            {
                dp[i+1][k] = (dp[i+1][k] + dp[i][j] * (C(infd,infd-k) * C(n-vac-infd,cure-infd+k) % mod) % mod * inC(n-vac,cure) % mod) % mod;
            } 
        }
    }

    int ans = 0;
    for(int i=1;i<=da;i++) ans = (ans + dp[i][0] * i) % mod;
    cout<<ans<<endl;

}