#include<iostream>
#include<cstring>
#include<cstdio>
#define md 1000000007
using namespace std;

int n,f[105][500],i,j,k,ok[505],ans;

int ya(int a,int b,int c,int d)
{
	return d+(c<<2)+(b<<4)+(a<<6);
}
void build_ok()
{
	for(int i=0;i<=3;i++)
	{
		ok[ya(i,1,2,3)]=1;
		ok[ya(i,1,3,2)]=1;
		ok[ya(i,2,1,3)]=1;
		ok[ya(1,i,2,3)]=1;
		ok[ya(1,2,i,3)]=1;
		ok[ya(1,2,3,i)]=1;
		ok[ya(1,3,2,i)]=1;
		ok[ya(2,1,3,i)]=1;
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	build_ok();
	for(i=0;i<(1<<6);i++)
		f[3][i<<2]=i==27||i==30||i==39?0:1;
	for(i=4;i<=n;i++)
	{
		for(j=0;j<(1<<8);j++)
			if(!ok[j])
				for(k=0;k<=3;k++)
					f[i][j]=(f[i][j]+f[i-1][((j<<2)&((1<<8)-1))|k])%md;
	}
	for(i=0;i<(1<<8);i++)
		ans=(ans+f[n][i])%md;
	cout<<ans;
	return 0;
}
### 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<cstring>
#include<cstdio>
#define md 1000000007
using namespace std;

int n,f[105][500],i,j,k,ok[505],ans;

int ya(int a,int b,int c,int d)
{
	return d+(c<<2)+(b<<4)+(a<<6);
}
void build_ok()
{
	for(int i=0;i<=3;i++)
	{
		ok[ya(i,1,2,3)]=1;
		ok[ya(i,1,3,2)]=1;
		ok[ya(i,2,1,3)]=1;
		ok[ya(1,i,2,3)]=1;
		ok[ya(1,2,i,3)]=1;
		ok[ya(1,2,3,i)]=1;
		ok[ya(1,3,2,i)]=1;
		ok[ya(2,1,3,i)]=1;
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	build_ok();
	for(i=0;i<(1<<6);i++)
		f[3][i<<2]=i==27||i==30||i==39?0:1;
	for(i=4;i<=n;i++)
	{
		for(j=0;j<(1<<8);j++)
			if(!ok[j])
				for(k=0;k<=3;k++)
					f[i][j]=(f[i][j]+f[i-1][((j<<2)&((1<<8)-1))|k])%md;
	}
	for(i=0;i<(1<<8);i++)
		ans=(ans+f[n][i])%md;
	cout<<ans;
	return 0;
}
```