#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
#define efor(i, l, r) for (int i = int(r) - 1; i >= int(l); i--)
#define nfor(i, n) efor(i, 0, n)
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
#define sz(a) int((a).size())
#define mp(x, y) make_pair((x), (y))
#define x first
#define y second

using namespace std;

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const ld EPS = 1e-9;

int reverse(int x, int logn) { // use own complex!!!
    int ans = 0;
    forn(i, logn) if (x & (1 << i)) ans |= 1 << (logn - 1 - i);
    return ans;
}

typedef complex<ld> base;
const ld PI = acosl(-1);

const int LOGN = 18, N = (1 << LOGN) + 3;
void fft(base a[N], int n, bool inv) {
    static base vv[LOGN][N];
    static bool prepared = false;
    if (!prepared) {
        prepared = true;
        forn(i, LOGN) {
            ld ang = 2 * PI / (1 << (i + 1));
            forn(j, 1 << i) vv[i][j] = base(cos(ang * j), sin(ang * j));
        }
    }
    int logn = 0; while ((1 << logn) < n) logn++;
    static base b[N];
    forn(i, n) b[i] = a[reverse(i, logn)];
    for (int i = 0; (1 << i) < n; i++)
        for (int j = 0; j < n; j += (1 << (i + 1)))
            for (int k = j; k < j + (1 << i); k++) {
                base cur = inv ? conj(vv[i][k - j]) : vv[i][k - j];
                base l = b[k], r = cur * b[k + (1 << i)];
                b[k] = l + r;
                b[k + (1 << i)] = l - r;
            }
    forn(i, n) a[i] = b[i] / ld(inv ? n : 1);
}

void mul(li a[N], int n, li b[N], int m, li ans[N]) {
    static base fp[N], p1[N], p2[N];
    int cnt = n + m;
    while (cnt & (cnt - 1)) cnt++;

    forn(i, cnt) fp[i] = base(i < n ? a[i] : 0, i < m ? b[i] : 0);
    fft(fp, cnt, false); // one can simply rework it
    forn(i, cnt) {       // with two calls of fft for p1, p2
        p1[i] = (fp[i] + conj(fp[(cnt - i) % cnt])) / base(2, 0);
        p2[i] = (fp[i] - conj(fp[(cnt - i) % cnt])) / base(0, 2);
    }
    forn(i, cnt) fp[i] = p1[i] * p2[i];
    fft(fp, cnt, true);

    forn(i, cnt) ans[i] = li(fp[i].real() + 0.5);
}

void mul(int* a, int* b, int n, const int mod) {
    int smod = int(sqrt((ld) mod));
    static li a1[N], a2[N], b1[N], b2[N], za[N], zb[N];
    forn(i, n) {
        a1[i] = a[i] % smod, a2[i] = a[i] / smod;
        b1[i] = b[i] % smod, b2[i] = b[i] / smod;
        za[i] = a1[i] + a2[i];
        zb[i] = b1[i] + b2[i];
    }
    mul(a1, n, b1, n, a1);
    mul(a2, n, b2, n, a2);
    mul(za, n, zb, n, za);
    forn(i, n) a[i] = 0;
    forn(i, 2 * n) {
        li cur = a[i % n];
        cur += a1[i] % mod;
        cur += a2[i] % mod * smod * smod % mod;
        cur += (za[i] - a1[i] - a2[i]) % mod * smod % mod;
        cur %= mod;
        a[i % n] = int(cur < 0 ? (cur + mod) : cur);
    }
}
int n;

bool read() {
    return !!(cin >> n);
}

const int m = 1000 * 1000 * 1000 + 7;

int gcd(int a, int b, int& x, int& y) {
    if (!a) {
        x = 0, y = 1;
        return b;
    }
    int xx, yy, g = gcd(b % a, a, xx, yy);
    x = yy - b / a * xx;
    y = xx;
    return g;
}

inline int inv(int a) {
    int x, y;
    assert(gcd(a, m, x, y) == 1);
    x %= m;
    (x < 0) && (x += m);
    return x;
}

inline int add(int a, int b) { return a + b >= m ? a + b - m : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + m : a - b; }
inline int mul(int a, int b) { return int(a * 1ll * b % m); }
inline void inc(int& a, int b) { a = add(a, b); }
inline void dec(int& a, int b) { a = sub(a, b); }

int fact[N], ifact[N];

inline int getC(int n, int k) {
    if (k < 0 || k >= n) return 0;
    return mul(fact[n], mul(ifact[k], ifact[n - k]));
}

int pw[N];
int z1[N], z2[N];
int a[N], b[N], ab[N];

void solve() {
    pw[0] = 1; fore(i, 1, N) pw[i] = mul(pw[i - 1], 4);
    fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i);
    forn(i, N) ifact[i] = inv(fact[i]);

    forn(k, N) {
        int v = getC(k, k / 2);
        z1[k] = (k & 1) ? 0 : mul(v, v);
    }

    int blen = 10000;

    int ans = 0;
    for (int i = 0; i <= n; i += blen) {
        int j = min(n + 1, i + blen);
        //cerr << i << ' ' << j << endl;
        forn(p, n + 1) a[p] = z1[p];
        forn(p, n + 1) b[p] = p < j ? z2[p] : 0;
        mul(a, b, n + 1, m);

        fore(k, i, j) {
            z2[k] = pw[k];
            dec(z2[k], int(a[k] % m));
            fore(l, i, k)
                dec(z2[k], mul(z1[k - l], z2[l]));
            inc(ans, mul(z2[k], pw[n - k]));
        }
    }

    cout << ans << endl;
}

int main() {
#ifdef SU1
    assert(freopen("input.txt", "rt", stdin));
    //assert(freopen("output.txt", "wt", stdout));
#endif

    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(6);

#ifdef SU1
    ld startTime = clock() / ld(CLOCKS_PER_SEC);
#endif

    while (read()) {
        solve();
        //break;
    }

#ifdef SU1
    cerr << " == Time: " << (clock() / ld(CLOCKS_PER_SEC) - startTime) << " == " << endl;
#endif

    return 0;
}