#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;
}