#include <bits/stdc++.h>
using namespace std;

long long MOD=1000000007;
vector<int> ng(64,-1);

int main(){
	int N;
	cin >> N;
	long long dp[N+1][64];
	for(int i=0;i<N+1;i++)for(int j=0;j<64;j++)dp[i][j]=0;
	for(int j=0;j<64;j++)dp[3][j]=1;
	dp[3][6]=0;dp[3][9]=0;dp[3][17]=0;
	
	ng[1]=6;ng[2]=9;ng[8]=33;ng[9]=37;ng[10]=41;ng[11]=45;
	ng[18]=9;ng[34]=9;ng[50]=9;ng[6]=25;ng[14]=57;ng[17]=6;
	ng[33]=6;ng[49]=6;ng[24]=33;ng[40]=33;ng[56]=33;
	
	for(int i=4;i<=N;i++){
		for(int j=0;j<64;j++){
			int p=j/16;
			int q=(j%16)/4;
			int r=j%4;
			int k=q*16+r*4;
			for(int K=0;K<4;K++){
				if(k!=ng[j]){
					dp[i][k]+=dp[i-1][j];
					if(dp[i][k]>=MOD)dp[i][k]-=MOD;
				}
				k++;
			}
		}
	}
	
	long long ans=0;
	for(int j=0;j<64;j++)ans+=dp[N][j];
	ans%=MOD;
	cout << ans << endl;
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

long long MOD=1000000007;
vector<int> ng(64,-1);

int main(){
	int N;
	cin >> N;
	long long dp[N+1][64];
	for(int i=0;i<N+1;i++)for(int j=0;j<64;j++)dp[i][j]=0;
	for(int j=0;j<64;j++)dp[3][j]=1;
	dp[3][6]=0;dp[3][9]=0;dp[3][17]=0;
	
	ng[1]=6;ng[2]=9;ng[8]=33;ng[9]=37;ng[10]=41;ng[11]=45;
	ng[18]=9;ng[34]=9;ng[50]=9;ng[6]=25;ng[14]=57;ng[17]=6;
	ng[33]=6;ng[49]=6;ng[24]=33;ng[40]=33;ng[56]=33;
	
	for(int i=4;i<=N;i++){
		for(int j=0;j<64;j++){
			int p=j/16;
			int q=(j%16)/4;
			int r=j%4;
			int k=q*16+r*4;
			for(int K=0;K<4;K++){
				if(k!=ng[j]){
					dp[i][k]+=dp[i-1][j];
					if(dp[i][k]>=MOD)dp[i][k]-=MOD;
				}
				k++;
			}
		}
	}
	
	long long ans=0;
	for(int j=0;j<64;j++)ans+=dp[N][j];
	ans%=MOD;
	cout << ans << endl;
	return 0;
}
```