#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1e9 + 7;
const int M = 4;

void updAdd(int& a, int b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}
int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}

int mult(int a, int b)
{
	return (LL) a * b % mod;
}

struct Matrix
{
	int a[M][M];
	
	Matrix()
	{
		FOR (i, 0, M)
			fill(a[i], a[i] + M, 0);
	}
	
	Matrix(int x)
	{
		FOR (i, 0, M)
		{
			FOR (j, 0, M)
			{
				a[i][j] = i == j ? x : 0;
			}
		}
	}
	
	Matrix operator *(const Matrix& m)
	{
		Matrix res;
		FOR (i, 0, M)
		{
			FOR (j, 0, M)
			{
				FOR (k, 0, M)
				{
					updAdd(res.a[i][j], mult(a[i][k], m.a[k][j]));
				}
			}
		}
		return res;
	}
};

Matrix binpow(Matrix a, int n)
{
	Matrix res(1);
	while(n)
	{
		if(n & 1)
			res = res * a;
		a = a * a;
		n /= 2;
	}
	return res;
}


/*
bool ok(VI p)
{
	int n = SZ(p);
	p.resize(2 * n);
	FOR(i, 0, n)
		p[2 * n - 1 - i] = p[i];
	
	FOR(a, 0, 2 * n)
	FOR(b, a + 1, 2 * n)
	FOR(c, b + 1, 2 * n)
	FOR(d, c + 1, 2 * n)
	{
		if(p[a] < p[c] && p[c] < p[d] && p[d] < p[b])
			return 0;
	}
	return 1;
}

void solve(int n)
{
	VI p(n);
	iota(ALL(p), 0);
	
	cout << n << endl;
	cerr << n << endl;
	
	int cnt = 0;
	do
	{
		if(ok(p))
		{
			FOR(i, 0, n)
				cout << p[i] << " ";
			cout << endl;
			cnt++;
		}
	}while(next_permutation(ALL(p)));
	
	cout << endl;
	cerr << cnt << endl;
}
*/

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
	
	Matrix A;
	A.a[0][0] = 2;
	A.a[0][2] = 1;
	A.a[0][3] = 2;
	A.a[1][0] = 1;
	A.a[2][1] = 1;
	A.a[3][3] = 1;
	
	
	VI a = {1, 1, 2, 6, 16};
	
	
	int n;
	while(cin >> n)
	{
		if(n < SZ(a))
		{
			cout << a[n] << "\n";
			continue;
		}
		Matrix B = binpow(A, n - 4);
		
		int res = 0;
		res = add(res, mult(B.a[0][0], 16));
		res = add(res, mult(B.a[0][1], 6));
		res = add(res, mult(B.a[0][2], 2));
		res = add(res, mult(B.a[0][3], 1));
		
		cout << res << "\n";
	}
	
	



	
	
	return 0;
}