#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1000000000;

ll dp[101][4][4][4];
//dp[ii][i][j][k]0='A',1='C',2='G',3='T';
int main()
{
	ll n;
	cin >> n;
	rep(i,4)
	rep(j,4)
	rep(k,4)
	{
		dp[0][i][j][k]=1;
	}
	dp[0][0][2][1] = 0;//AGC
	dp[0][0][1][2] = 0;//ACG
	dp[0][2][0][1] = 0;//GAC

	rep(ii,100)
	{
		rep(i,4)
		{
			rep(j,4)
			{
				rep(k,4)
				{
					rep(x,4)
					{
						if(j==0&&k==2&&x==1)continue;
						if(j==0&&k==1&&x==2)continue;
						if(j==2&&k==0&&x==1)continue;
						if(i==0&&j==2&&x==1)continue;
						if(i==0&&k==2&&x==1)continue;
						dp[ii+1][j][k][x] = (dp[ii][i][j][k]+dp[ii+1][j][k][x])%MOD;
					}
				}
			}
		}
	}
	ll ans = 0;
	rep(i,4)rep(j,4)rep(k,4)ans = (ans + dp[n-3][i][j][k])%MOD;
	cout<<ans<<endl;
	return 0;
}
### 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;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1000000000;

ll dp[101][4][4][4];
//dp[ii][i][j][k]0='A',1='C',2='G',3='T';
int main()
{
	ll n;
	cin >> n;
	rep(i,4)
	rep(j,4)
	rep(k,4)
	{
		dp[0][i][j][k]=1;
	}
	dp[0][0][2][1] = 0;//AGC
	dp[0][0][1][2] = 0;//ACG
	dp[0][2][0][1] = 0;//GAC

	rep(ii,100)
	{
		rep(i,4)
		{
			rep(j,4)
			{
				rep(k,4)
				{
					rep(x,4)
					{
						if(j==0&&k==2&&x==1)continue;
						if(j==0&&k==1&&x==2)continue;
						if(j==2&&k==0&&x==1)continue;
						if(i==0&&j==2&&x==1)continue;
						if(i==0&&k==2&&x==1)continue;
						dp[ii+1][j][k][x] = (dp[ii][i][j][k]+dp[ii+1][j][k][x])%MOD;
					}
				}
			}
		}
	}
	ll ans = 0;
	rep(i,4)rep(j,4)rep(k,4)ans = (ans + dp[n-3][i][j][k])%MOD;
	cout<<ans<<endl;
	return 0;
}
```