#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

namespace {

constexpr int mod = 1'000'000'007;
constexpr int maxn = 14'000'000 + 5;

inline constexpr int mul(int64_t a, int64_t b) {
    return static_cast<int>(a * b % mod);
}
inline constexpr int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}
inline constexpr int qpow(int a, int64_t k) {
    int r = 1 % mod;
    while (k) {
        if (k & 1) r = mul(r, a);
        k >>= 1; a = mul(a, a);
    }
    return r;
}

int _inv[maxn], ifac[maxn], fac[maxn];

inline int inv(int a) {
    if (a < maxn) return _inv[a];
    return qpow(a, mod - 2);
}

inline int comb(int a, int b) {
    if (b < 0 || a < b) return 0;
    return mul(fac[a], mul(ifac[b], ifac[a - b]));
}

void pre() {
    fac[0] = 1;
    for (int i = 1; i < maxn; ++i)
        fac[i] = mul(fac[i - 1], i);
    ifac[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; --i)
        ifac[i] = mul(ifac[i + 1], i + 1);
    for (int i = 1; i < maxn; ++i)
        _inv[i] = mul(ifac[i], fac[i - 1]);
}

int dp[2][maxn];

} // namespace

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    pre();
    int n, ans = 0; cin >> n;

    int me = 0, he = 1;
    dp[me][1] = 1;

    int two = 1, three = 1;
    for (int i = 0; true; ++i) {

        bool alldone = true;
        for (int j = 1; j <= two; ++j)
            alldone &= dp[me][j] == 0;
        if (alldone) break;
        
        memset(dp[he], 0, sizeof(int) * (two * 2 + 1));
        for (int j = 0; j <= two; j++) {
            int &x = dp[he][min(j * 2, n - three)];
            x = add(x, dp[me][j]);
        }
        swap(me, he);

        memset(dp[he], 0, sizeof(int) * (two * 2 + 1));
        int c = n - three;
        int l = min(three * 2, n - three);
        int iv = inv(comb(c, l));
        for (int j = 0; j <= two * 2; j++) {
            for (int k = 0; k <= j; k++) {
                int coef = mul(comb(j, j - k), comb(c - j, l - (j - k)));
                dp[he][k] = add(dp[he][k], mul(coef, dp[me][j]));
            }
        }
        for (int j = 0; j <= two * 2; ++j)
            dp[he][k] = mul(dp[he][k], iv);
        swap(me, he);

        three *= 3;
        two *= 2;

        for (int j = 1; j <= two; j++) {
            ans = add(ans, dp[me][j]);
        }
    }


    cout << add(ans, 1) << '\n';
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:86:20: error: ‘k’ was not declared in this scope
   86 |             dp[he][k] = mul(dp[he][k], iv);
      |                    ^