You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:

* The string does not contain characters other than `A`, `C`, `G` and `T`.
* The string does not contain `AGC` as a substring.
* The condition above cannot be violated by swapping two adjacent characters once.

Constraints

* 3 \leq N \leq 100

Input

Input is given from Standard Input in the following format:


N


Output

Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

Examples

Input

3


Output

61


Input

4


Output

230


Input

100


Output

388130742
#include<iostream>
using namespace std;

const int mod = (int)1e9 + 7;
typedef long long ll;

ll dp[101][4][4][4];
int n;

void solve() {
	for (ll i = 3; i < n; i++) {
		for(int a = 0;a<4;a++)
			for(int g=0;g<4;g++)
				for(int c=0;c<4;c++)
					for (int d = 0; d < 4; d++) {
						if (a == 0 && c == 2 && d == 3)continue;
						if (a == 0 && g == 2 && d == 3)continue;
						if (g == 2 && c == 0 && d == 3)continue;
						if (g == 0 && c == 2 && d == 3)continue;
						if (g == 0 && c == 3 && d == 2)continue;
						dp[i][g][c][d] += dp[i - 1][a][g][c]%mod;
					}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++)for (int k = 0; k < 4; k++)
		dp[2][i][j][k] = 1;
	dp[2][0][2][3] = dp[2][0][3][2] = dp[2][2][0][3] = 0;
	solve();

	ll sum = 0;
	for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++)for (int k = 0; k < 4; k++)
		sum += dp[n - 1][i][j][k];
	
	cout << sum%mod << endl;

	return 0;
}