#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 1000000007
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
#define db long double
const int maxn = 13000005;
const int S = 50;
const int D = 200005;
int n;
ll p[S][D];
ll jc[maxn], bjc[maxn];
ll c(int a, int b) {
    if (b < 0) return 0;
    if (b > a) return 0;
    return jc[a] * bjc[b] % mod * bjc[a - b] % mod;
}
ll bc(int a, int b)
{
    if (b < 0)
        return 0;
    if (b > a)
        return 0;
    return bjc[a] * jc[b] % mod * jc[a - b] % mod;
}
int main() {
    jc[0] = 1;
    for (int i = 1; i < maxn; i++) jc[i] = jc[i - 1] * i % mod;
    bjc[maxn - 1] = ksm(jc[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--) 
        bjc[i] = bjc[i + 1] * (i + 1) % mod;
    
    int n;
    cin >> n;
    p[0][1] = 1;
    int good = 1;
    ll ans = 0;
    for (int i = 1; i < S; i++) {
        int rem = n - good;
        if (rem == 0) break;
        good *= 3;
        chkmin(good, n);
        int newrem = n - good;
        int bg = 0;
        for (int k = 0; k < D; k++) {
            if (p[i - 1][k]) {
                bg = k;
                int nw = min(2 * k, rem);
                for (int j = 0; j <= nw; j++)
                    p[i][j] += 1ll * p[i - 1][k] * c(nw, j) % mod * c(rem - nw, newrem - j) % mod * bc(rem, newrem) % mod, 
                    p[i][j] %= mod;
            }
        }
       // cout << bg << endl;
        for (int k = 1; k <= n; k++)
            ans += p[i][k], ans %= mod;
    }
    ans = (ans + 1) % mod;
    cout << ans << endl;
    return 0;
}
/*
1
1.6666 (5/3)
1.8333 (11/6)
1.9 (19/10)
1.9333 (29/15)
1.95238 (41/21)
1.96154 (55/28)

2.41667 = 29/12
2.63175 = 41/15

*/