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;
int N;
long mod=1e9+7,dp[101][64];
int main()
{
	cin>>N;
	dp[0][63]=1;
	for(int i=0;i<N;i++)for(int j=0;j<64;j++)
	{
		int a=j/16,b=j/4%4,c=j%4;
		for(int d=0;d<4;d++)
		{
			if(b==0&&c==2&&d==1)continue;
			if(a==0&&c==2&&d==1)continue;
			if(b==2&&c==0&&d==1)continue;
			if(b==0&&c==1&&d==2)continue;
			if(a==0&&b==2&&d==1)continue;
			(dp[i+1][b*16+c*4+d]+=dp[i][j])%=mod;
		}
	}
	long ans=0;
	for(int i=0;i<64;i++)ans+=dp[N][i];
	cout<<ans%mod<<endl;
}
