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

ll dp[110][4][4][4];

int main(){
	ll n;
	cin>>n;
	for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)dp[3][i][j][k]=1;
	//A=0,T=1,G=2,C=3;
	dp[3][0][2][3]=dp[3][0][3][2]=dp[3][2][0][3]=0;
	ll mod=1e9+7;

	for(int i=4;i<=n;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					for(int m=0;m<4;m++){
						if(k==0&&l==2&&m==3)continue;
						if(k==0&&l==3&&m==2)continue;
						if(k==2&&l==0&&m==3)continue;
						if(j==0&&l==2&&m==3)continue;
						if(j==0&&k==2&&m==3)continue;
						dp[i][k][l][m]+=dp[i-1][j][k][l];
						dp[i][k][l][m]%=mod;
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++){
		ans+=dp[n][i][j][k];
		ans%=mod;
	}
	cout<<ans;
	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;
typedef long long ll;

ll dp[110][4][4][4];

int main(){
	ll n;
	cin>>n;
	for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)dp[3][i][j][k]=1;
	//A=0,T=1,G=2,C=3;
	dp[3][0][2][3]=dp[3][0][3][2]=dp[3][2][0][3]=0;
	ll mod=1e9+7;

	for(int i=4;i<=n;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					for(int m=0;m<4;m++){
						if(k==0&&l==2&&m==3)continue;
						if(k==0&&l==3&&m==2)continue;
						if(k==2&&l==0&&m==3)continue;
						if(j==0&&l==2&&m==3)continue;
						if(j==0&&k==2&&m==3)continue;
						dp[i][k][l][m]+=dp[i-1][j][k][l];
						dp[i][k][l][m]%=mod;
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++){
		ans+=dp[n][i][j][k];
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

```