#include<iostream>
#include<algorithm>
using namespace std;
int n;
long mod=1e9+7,dp[111][64];
int main()
{
	cin>>n;
	dp[0][63]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<64;j++)
		{
			string T="";
			int o=j;
			for(int k=0;k<3;k++)
			{
				T+="ACGT"[o%4];
				o/=4;
			}
			reverse(T.begin(),T.end());
			for(int k=0;k<4;k++)
			{
				string now=T;
				now+="ACGT"[k];
				bool flag=false;
				flag|=now[0]=='A'&&now[2]=='G'&&now[3]=='C';
				flag|=now[0]=='A'&&now[1]=='G'&&now[3]=='C';
				flag|=now[1]=='G'&&now[2]=='A'&&now[3]=='C';
				flag|=now[1]=='A'&&now[2]=='C'&&now[3]=='G';
				flag|=now[1]=='A'&&now[2]=='G'&&now[3]=='C';
				if(flag)continue;
				int comv=0;
				for(int l=1;l<4;l++)comv=comv*4+
					(now[l]=='A'?0:now[l]=='C'?1:now[l]=='G'?2:3);
				dp[i][comv]+=dp[i-1][j];
				dp[i][comv]%=mod;
			}
		}
	}
	long ans=0;
	for(int i=0;i<64;i++)
	{
		ans+=dp[n][i];
		ans%=mod;
	}
	cout<<ans<<endl;
}
### Prompt

Create a solution in Cpp for 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<iostream>
#include<algorithm>
using namespace std;
int n;
long mod=1e9+7,dp[111][64];
int main()
{
	cin>>n;
	dp[0][63]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<64;j++)
		{
			string T="";
			int o=j;
			for(int k=0;k<3;k++)
			{
				T+="ACGT"[o%4];
				o/=4;
			}
			reverse(T.begin(),T.end());
			for(int k=0;k<4;k++)
			{
				string now=T;
				now+="ACGT"[k];
				bool flag=false;
				flag|=now[0]=='A'&&now[2]=='G'&&now[3]=='C';
				flag|=now[0]=='A'&&now[1]=='G'&&now[3]=='C';
				flag|=now[1]=='G'&&now[2]=='A'&&now[3]=='C';
				flag|=now[1]=='A'&&now[2]=='C'&&now[3]=='G';
				flag|=now[1]=='A'&&now[2]=='G'&&now[3]=='C';
				if(flag)continue;
				int comv=0;
				for(int l=1;l<4;l++)comv=comv*4+
					(now[l]=='A'?0:now[l]=='C'?1:now[l]=='G'?2:3);
				dp[i][comv]+=dp[i-1][j];
				dp[i][comv]%=mod;
			}
		}
	}
	long ans=0;
	for(int i=0;i<64;i++)
	{
		ans+=dp[n][i];
		ans%=mod;
	}
	cout<<ans<<endl;
}
```