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 <bits/stdc++.h>
#define ll long long 
using namespace std;
const ll MOD=1e9+7; //定义MOD代替1e9+7
int n;
ll dp[101][4][4][4],ans; 
int main()
{
	cin>>n;
	dp[0][3][3][3]=1;
	for (int len=1;len<=n;++len)
		for (int i=0;i<4;++i)
			for (int j=0;j<4;++j)
				for (int k=0;k<4;++k)
					for (int l=0;l<4;++l)
					{
						if (j==0 && k==2 && l==1) continue;
						if (j==2 && k==0 && l==1) continue;
						if (j==0 && k==1 && l==2) continue;
						if (i==0 && k==2 && l==1) continue;
						if (i==0 && j==2 && l==1) continue;
						dp[len][j][k][l]+=dp[len-1][i][j][k];
						dp[len][j][k][l]%=MOD;
					}
	for (int i=0;i<4;++i)
		for (int j=0;j<4;++j)
			for (int k=0;k<4;++k)
				ans+=dp[n][i][j][k],ans%=MOD;
	cout<<ans;
	return 0;
}