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>
using namespace std;

typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD = 1e9+7;

ll dp[105][5][5][5];

int main(){
	int n;
	cin >> n;
	
	dp[0][0][0][0] = 1;
	rep(i,n) rep(j,5) rep(k,5) rep(l,5){
		rep(m,4){
			dp[i+1][k][l][m+1] += dp[i][j][k][l];
			dp[i+1][k][l][m+1] %= MOD;
		}
		if((j==1&&k==3)||(j==1&&l==3)||(k==3&&l==1)||(k==1&&l==3)){
			dp[i+1][k][l][2] += MOD-dp[i][j][k][l];
			dp[i+1][k][l][2] %= MOD;
		}
	
		if(k==1&&l==2){
			dp[i+1][k][l][3] += MOD-dp[i][j][k][l];
			dp[i+1][k][l][3] %= MOD;
		}
	}

	ll ans = 0;
	rep(i,4) rep(j,4) rep(k,4) (ans+=dp[n][i+1][j+1][k+1])%=MOD;
	cout << ans << endl;

	return 0;
}