#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int n,f[110][5][5][5],ans;
int main()
{
	scanf("%d",&n);
	for(register int i=0;i<4;i++)
		for(register int j=0;j<4;j++)
			for(register int k=0;k<4;k++)
				f[3][i][j][k]=1;
	f[3][0][2][1]=0;
	f[3][0][1][2]=0;
	f[3][2][0][1]=0;
	for(register int i=4;i<=n;i++)
		for(register int a1=0;a1<4;a1++)
			for(register int a2=0;a2<4;a2++)
				for(register int a3=0;a3<4;a3++)
					for(register int a4=0;a4<4;a4++)
					{
						if(a1==0 && a3==2 && a4==1 || a2==2 && a3==0 && a4==1 || a2==0 && a3==2 && a4==1 || a2==0 && a3==1 && a4==2 || a1==0 && a2==2 && a4==1)
						continue;
						(f[i][a2][a3][a4]+=f[i-1][a1][a2][a3])%=Mod;
					}
	for(register int i=0;i<4;i++)
		for(register int j=0;j<4;j++)
			for(register int k=0;k<4;k++)
				(ans+=f[n][i][j][k])%=Mod;
	printf("%d",ans);
	return 0;
}
### Prompt

Please formulate a Cpp solution 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;
const int Mod=1e9+7;
int n,f[110][5][5][5],ans;
int main()
{
	scanf("%d",&n);
	for(register int i=0;i<4;i++)
		for(register int j=0;j<4;j++)
			for(register int k=0;k<4;k++)
				f[3][i][j][k]=1;
	f[3][0][2][1]=0;
	f[3][0][1][2]=0;
	f[3][2][0][1]=0;
	for(register int i=4;i<=n;i++)
		for(register int a1=0;a1<4;a1++)
			for(register int a2=0;a2<4;a2++)
				for(register int a3=0;a3<4;a3++)
					for(register int a4=0;a4<4;a4++)
					{
						if(a1==0 && a3==2 && a4==1 || a2==2 && a3==0 && a4==1 || a2==0 && a3==2 && a4==1 || a2==0 && a3==1 && a4==2 || a1==0 && a2==2 && a4==1)
						continue;
						(f[i][a2][a3][a4]+=f[i-1][a1][a2][a3])%=Mod;
					}
	for(register int i=0;i<4;i++)
		for(register int j=0;j<4;j++)
			for(register int k=0;k<4;k++)
				(ans+=f[n][i][j][k])%=Mod;
	printf("%d",ans);
	return 0;
}
```