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

int n;
int md=1000000007;
int dp[102][5][5][5];

bool ck(int a,int b,int c,int d){
	int t[4]={a,b,c,d};

	if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
	if(t[1]==0 && t[2]==1 && t[3]==2)return(false);

	for(int cc=0;cc<3;cc++){
		swap(t[cc],t[cc+1]);
		if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
		if(t[1]==0 && t[2]==1 && t[3]==2)return(false);
		swap(t[cc],t[cc+1]);
	}

	return(true);
}

int slv(int now,int pre3,int pre2,int pre1){
	long long ret = 0ll;

	if(now==n) return(1);
	if(dp[now][pre3][pre2][pre1] != -1) return(dp[now][pre3][pre2][pre1]);

	for(int i=0;i<4;i++){
		if(ck(pre3,pre2,pre1,i)){
			ret = (ret+slv(now+1,pre2,pre1,i))%md;
		}
	}

	return(dp[now][pre3][pre2][pre1] = ret);
}

int main(){

	for(int i=0;i<102;i++){for(int j=0;j<5;j++){for(int k=0;k<5;k++){for(int l=0;l<5;l++){dp[i][j][k][l]=-1;}}}}

	cin>>n;
	int ans = slv(0,3,3,3);
	cout<<ans<<endl;

	return(0);
}
### Prompt

Please create a solution in cpp to the following problem:

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;

int n;
int md=1000000007;
int dp[102][5][5][5];

bool ck(int a,int b,int c,int d){
	int t[4]={a,b,c,d};

	if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
	if(t[1]==0 && t[2]==1 && t[3]==2)return(false);

	for(int cc=0;cc<3;cc++){
		swap(t[cc],t[cc+1]);
		if(t[0]==0 && t[1]==1 && t[2]==2)return(false);
		if(t[1]==0 && t[2]==1 && t[3]==2)return(false);
		swap(t[cc],t[cc+1]);
	}

	return(true);
}

int slv(int now,int pre3,int pre2,int pre1){
	long long ret = 0ll;

	if(now==n) return(1);
	if(dp[now][pre3][pre2][pre1] != -1) return(dp[now][pre3][pre2][pre1]);

	for(int i=0;i<4;i++){
		if(ck(pre3,pre2,pre1,i)){
			ret = (ret+slv(now+1,pre2,pre1,i))%md;
		}
	}

	return(dp[now][pre3][pre2][pre1] = ret);
}

int main(){

	for(int i=0;i<102;i++){for(int j=0;j<5;j++){for(int k=0;k<5;k++){for(int l=0;l<5;l++){dp[i][j][k][l]=-1;}}}}

	cin>>n;
	int ans = slv(0,3,3,3);
	cout<<ans<<endl;

	return(0);
}
```