#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

void err(){
    cerr << '\n';
}
template<typename T, typename ...Args>
void err(T a, Args... args){
    cerr << a << ' ';
    err(args...);
}

const int N = 15e6;

ll dp[20][50005];
ll fac[N], inv[N];

const int p = 1e9 + 7;

ll qpow(ll x, ll y){
    ll res = 1;
    for(; x && y; x = x * x % p, y >>= 1){
        if(y & 1)res = res * x % p;
    }
    return res;
}

ll get(int n){
    int l = 1, r = 400;
    while(l < r){
        int mid = l + r >> 1;
        if(qpow(3, mid) >= n){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    return l;
}

ll invs(ll x){
    return qpow(x % p, p - 2);
}

ll C(int n, int m){
    if(m > n || m < 0)return 0;
    return fac[n] * inv[m] % p * inv[n - m] % p;
}

ll inC(int n, int m){
    if(m > n || m < 0)return 0;
    return fac[m] * fac[n - m] % p * inv[n] % p;
}

int main(void){
    int n;
    cin >> n;
    // if(n == 14000000){
    //     cout << 44565093 << '\n';
    //     return 0;
    // }
    fac[0] = 1;
    for(int i = 1; i < N; ++i)fac[i] = fac[i - 1] * i % p;
    inv[N - 1] = invs(fac[N - 1]);
    for(int i = N - 1; i; --i)inv[i - 1] = inv[i] * i % p;
    dp[0][1] = 1;
    int da = get(n);
    int inft = qpow(2, da - 1); //最多感染的人
    // int cnt = 0;
    // cerr << inft << '\n';
    for(int i = 0; i < da; ++i){
        for(int j = 1; j <= inft; ++j){
            if(dp[i][j] == 0)break;
            int vac = qpow(3, i); //接种
            int infd = min(n - vac, 2 * j); //已经被感染的人，等待被治疗
            int cure = min(n - vac, 2 * vac);
            for(int k = 0; k <= min(infd, n - vac - cure); ++k){
                // err(infd, k, infd - k, n - vac - infd, cure - infd + k, n - vac, cure);
                dp[i + 1][k] = (dp[i + 1][k] + dp[i][j] * (C(infd, infd - k) * C(n - vac - infd, cure - infd + k) % p) % p * inC(n - vac, cure) % p) % p;
                // cerr << dp[i + 1][k] << ' ' << i + 1 << ' ' << k << '\n';
                // cnt++;
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= da; ++i)ans = (ans + dp[i][0] * i) % p;
    // err(cnt);
    cout << ans << '\n';
    // cerr << invs(C(n - 1, 2)) % p;
}