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 rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

const int MOD=1000000007;

string ng[]{"AGC","GAC","ACG","A*GC","AG*C"};
int dp[200][4][4][4];
map<char,int>id={{'A',0},{'C',1},{'G',2},{'T',3}};

bool match(vector<int>a){
	rep(i,3){
		bool ok=true;
		rep(j,3){
			if(a[j+1]!=id[ng[i][j]])ok=false;
		}
		if(ok)return true;
	}
	for(int i=3;i<5;i++){
		bool ok=true;
		rep(j,4){
			if(ng[i][j]!='*'&&a[j]!=id[ng[i][j]])ok=false;
		}
		if(ok)return true;
	}
	return false;
}

int main(){
	int n;cin>>n;
	dp[0][3][3][3]=1;
	rep(i,n)rep(j,4)rep(k,4)rep(t,4){
		int D=dp[i][j][k][t];
		rep(nx,4){
			if(match({j,k,t,nx}))continue;
			(dp[i+1][k][t][nx]+=D)%=MOD;
		}
	}
	int ans=0;
	rep(i,4)rep(j,4)rep(k,4)(ans+=dp[n][i][j][k])%=MOD;
	cout<<ans<<endl;
}