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 dp[101][4][4][4];
int mod=1000000007;
int N;
int main() {
	cin>>N;
	dp[0][3][3][3]=1;
	for(int len=0;len<N;len++){
//		cout<<"len="<<len<<endl;
		for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++){
			if(dp[len][a][b][c]==0)continue;
			if(a==0&&b==1&&c==2)continue;
			if(a==1&&b==0&&c==2)continue;
			if(a==0&&b==2&&c==1)continue;
			for(int d=0;d<4;d++){
				if(b==0&&c==1&&d==2)continue;
				if(b==1&&c==0&&d==2)continue;
				if(b==0&&c==2&&d==1)continue;
				if(a==0&&c==1&&d==2)continue;
				if(a==0&&b==1&&d==2)continue;
//				cout<<len<<":"<<a<<":"<<b<<":"<<c<<":"<<d<<endl;
				dp[len+1][b][c][d] += dp[len][a][b][c];
				dp[len+1][b][c][d] %= mod;
			}
		}
	}
	int ans=0;
	for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++){
		ans += dp[N][a][b][c];
		ans %= mod;
	}
	cout<<ans;
	return 0;
}