#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
//A 1
//G 2
//C 3
//T 4
int n,ans;
map<pair<pair<int,int>,pair<int,int> >,int> mem;
int dfs(int x,int a,int b,int c)
{
	if(x>=n)
		return 1;
	if(mem[make_pair(make_pair(x,a),make_pair(b,c))])
		return mem[make_pair(make_pair(x,a),make_pair(b,c))];
	int res=0;
	for(int l=1;l<=4;l++)
	{
		if(l==3&&(b==1&&c==2||a==1&&b==2||a==1&&c==2||b==2&&c==1)) continue;
		if(l==2&&b==1&&c==3) continue;
		res+=dfs(x+1,b,c,l);
		res%=mod;
	}
	mem[make_pair(make_pair(x,a),make_pair(b,c))]=res;
	return res;
}
signed main()
{
	cin>>n;
	if(n==3)
	{
		cout<<61<<endl;
		return 0;
	}
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			for(int k=1;k<=4;k++)
			{
				if(i==1&&j==2&&k==3||i==2&&j==1&&k==3||i==1&&j==3&&k==2) continue;
				ans+=dfs(3,i,j,k);
				ans%=mod;
			}
	cout<<ans<<endl;
	return 0;
}

### Prompt

In cpp, your task is to solve 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;
#define int long long
#define mod 1000000007
//A 1
//G 2
//C 3
//T 4
int n,ans;
map<pair<pair<int,int>,pair<int,int> >,int> mem;
int dfs(int x,int a,int b,int c)
{
	if(x>=n)
		return 1;
	if(mem[make_pair(make_pair(x,a),make_pair(b,c))])
		return mem[make_pair(make_pair(x,a),make_pair(b,c))];
	int res=0;
	for(int l=1;l<=4;l++)
	{
		if(l==3&&(b==1&&c==2||a==1&&b==2||a==1&&c==2||b==2&&c==1)) continue;
		if(l==2&&b==1&&c==3) continue;
		res+=dfs(x+1,b,c,l);
		res%=mod;
	}
	mem[make_pair(make_pair(x,a),make_pair(b,c))]=res;
	return res;
}
signed main()
{
	cin>>n;
	if(n==3)
	{
		cout<<61<<endl;
		return 0;
	}
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			for(int k=1;k<=4;k++)
			{
				if(i==1&&j==2&&k==3||i==2&&j==1&&k==3||i==1&&j==3&&k==2) continue;
				ans+=dfs(3,i,j,k);
				ans%=mod;
			}
	cout<<ans<<endl;
	return 0;
}

```