#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[101][4][4][4];
int mod=1e9+7;
int main(){
	int n;
	cin>>n;
	dp[0][3][3][3]=1;
	for(int len=0;len<n;len++)
	 
	 	for(int c1=0;c1<4;c1++)
	 	
	 		for(int c2=0;c2<4;c2++)
	 		
	 			for(int c3=0;c3<4;c3++)
	 			
	 			{
					 	if(dp[len][c1][c2][c3]==0)continue;
	 				for(int a=0;a<4;a++)
	 				{
					 
	 					if(a==2&&c1==1&&c2==0)continue;
	 					if(a==2&&c1==0&&c2==1)continue;
	 					if(a==1&&c1==2&&c2==0)continue;
	 					if(a==2&&c1==1&&c3==0)continue;
	 					if(a==2&&c2==1&&c3==0)continue;
	 					dp[len+1][a][c1][c2]+=dp[len][c1][c2][c3];
						dp[len+1][a][c1][c2]%=mod;  }
			}
	 int ans=0;
	 for(int c1=0;c1<4;c1++)
	 
	 	for(int c2=0;c2<4;c2++)
	 	
	 		for(int c3=0;c3<4;c3++)
	 		
	 			{
				 ans+=dp[n][c1][c2][c3];
	 			ans%=mod;}
	
	 cout<<ans<<endl;
} 
### 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;
int dp[101][4][4][4];
int mod=1e9+7;
int main(){
	int n;
	cin>>n;
	dp[0][3][3][3]=1;
	for(int len=0;len<n;len++)
	 
	 	for(int c1=0;c1<4;c1++)
	 	
	 		for(int c2=0;c2<4;c2++)
	 		
	 			for(int c3=0;c3<4;c3++)
	 			
	 			{
					 	if(dp[len][c1][c2][c3]==0)continue;
	 				for(int a=0;a<4;a++)
	 				{
					 
	 					if(a==2&&c1==1&&c2==0)continue;
	 					if(a==2&&c1==0&&c2==1)continue;
	 					if(a==1&&c1==2&&c2==0)continue;
	 					if(a==2&&c1==1&&c3==0)continue;
	 					if(a==2&&c2==1&&c3==0)continue;
	 					dp[len+1][a][c1][c2]+=dp[len][c1][c2][c3];
						dp[len+1][a][c1][c2]%=mod;  }
			}
	 int ans=0;
	 for(int c1=0;c1<4;c1++)
	 
	 	for(int c2=0;c2<4;c2++)
	 	
	 		for(int c3=0;c3<4;c3++)
	 		
	 			{
				 ans+=dp[n][c1][c2][c3];
	 			ans%=mod;}
	
	 cout<<ans<<endl;
} 
```