#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,maxn=200;
int f[maxn][4][4][4];
/*
A 0
G 1
C 2
T 3

012
0 12
102
021
01 2

012
021
102
*/
signed main(){
	int i,j,k,m,n,u,v;
	cin>>n;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++){
			f[3][i][j][k]=1;
		}
	f[3][2][1][0]=f[3][1][2][0]=f[3][2][0][1]=0;
	for(i=4;i<=n;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++)
				for(u=0;u<4;u++)
					for(v=0;v<4;v++){
						if(v==2&&u==1&&k==0)continue;
						if(v==1&&u==2&&k==0)continue;
						if(v==2&&u==0&&k==1)continue;
						if(v==2&&u==1&&j==0)continue;
						if(v==2&&k==1&&j==0)continue;
						f[i][v][u][k]+=f[i-1][u][k][j];
						f[i][v][u][k]%=mod;
				}
	int sum=0;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++){
			sum+=f[n][k][j][i];
			sum%=mod;
		}
	printf("%lld\n",sum%mod);	
	return 0;
}
### Prompt

Your challenge is to write 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>
#define int long long
using namespace std;
const int mod=1e9+7,maxn=200;
int f[maxn][4][4][4];
/*
A 0
G 1
C 2
T 3

012
0 12
102
021
01 2

012
021
102
*/
signed main(){
	int i,j,k,m,n,u,v;
	cin>>n;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++){
			f[3][i][j][k]=1;
		}
	f[3][2][1][0]=f[3][1][2][0]=f[3][2][0][1]=0;
	for(i=4;i<=n;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++)
				for(u=0;u<4;u++)
					for(v=0;v<4;v++){
						if(v==2&&u==1&&k==0)continue;
						if(v==1&&u==2&&k==0)continue;
						if(v==2&&u==0&&k==1)continue;
						if(v==2&&u==1&&j==0)continue;
						if(v==2&&k==1&&j==0)continue;
						f[i][v][u][k]+=f[i-1][u][k][j];
						f[i][v][u][k]%=mod;
				}
	int sum=0;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			for(k=0;k<4;k++){
			sum+=f[n][k][j][i];
			sum%=mod;
		}
	printf("%lld\n",sum%mod);	
	return 0;
}
```