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 MOD 1000000007
using namespace std;
long long dp[105][4][4][4],ans;
bool check(int a,int b,int c)
{
	if(a==1&&b==2&&c==3)
		return true;
	else
		return false;
}
int main(){
	int n,i,a,b,c,d;
	cin>>n;
	memset(dp,0,sizeof(dp));
	dp[0][0][0][0]=1;
	for(i=0;i<n;i++)
		for(a=0;a<4;a++)
			for(b=0;b<4;b++)
				for(c=0;c<4;c++)
					for(d=0;d<4;d++)
					{
						if(check(a,b,c)||check(a,c,d)||check(a,b,d)||check(b,c,d))
							continue;
						if(check(c,b,d)||check(b,d,c))
							continue;
						dp[i+1][b][c][d]+=dp[i][a][b][c];
						dp[i+1][b][c][d]%=MOD;
					}
	ans=0;
	for(a=0;a<4;a++)
		for(b=0;b<4;b++)
			for(c=0;c<4;c++)
				ans=(ans+dp[n][a][b][c])%MOD;
	cout<<ans<<endl;
	return 0;
}