#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 1
#define INF (1LL<<50)
#define MOD 1000000007

map<lli,map<string,lli>> memo;
lli n;

bool ok(string last4){
	for(lli i=0;i<4;i++){
		string t = last4;
		if(i>=1)swap(t[i-1],t[i]);
		if(t.find("AGC")!=-1)return false;
	}
	return true;
}

lli func(lli now,string last3){
	if(memo[now][last3])return memo[now][last3];
	if(now == n)return 1;

	lli ret = 0;
	string s="AGCT";

	REP(i,0,4){
		string next4 = last3+s.substr(i,1);
		if(ok(next4))ret += func(now+1,next4.substr(1,3));
	}
	ret %= MOD;
	return memo[now][last3]=ret;
}

signed main(){

	cin>>n;

	cout<<func(0,"TTT")%MOD<<endl;

	return 0;
}
### Prompt

Your task is to create 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;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 1
#define INF (1LL<<50)
#define MOD 1000000007

map<lli,map<string,lli>> memo;
lli n;

bool ok(string last4){
	for(lli i=0;i<4;i++){
		string t = last4;
		if(i>=1)swap(t[i-1],t[i]);
		if(t.find("AGC")!=-1)return false;
	}
	return true;
}

lli func(lli now,string last3){
	if(memo[now][last3])return memo[now][last3];
	if(now == n)return 1;

	lli ret = 0;
	string s="AGCT";

	REP(i,0,4){
		string next4 = last3+s.substr(i,1);
		if(ok(next4))ret += func(now+1,next4.substr(1,3));
	}
	ret %= MOD;
	return memo[now][last3]=ret;
}

signed main(){

	cin>>n;

	cout<<func(0,"TTT")%MOD<<endl;

	return 0;
}
```