#include<iostream>
#include<map>
using namespace std;
const int mod=1000000007;
int n;
map<string,long> dp[101];

bool ok(string s){
	for(int i=0;i<4;i++){
		string s4=s;
		if(i!=0){
			char tmp=s4[i];
			s4[i]=s4[i-1];
			s4[i-1]=tmp;
		}
		if(s4.substr(0,3)=="AGC" || s4.substr(1)=="AGC") return false;
	}
	return true;
}

string ss="ACGT";
long dfs(int cur,string s3){
	if(dp[cur].count(s3)) return dp[cur][s3];
	if(cur==n) return 1;
	long res=0;
	for(char c:ss){
		if(ok(s3+c)) res+=dfs(cur+1,s3.substr(1)+c);
	}
	return dp[cur][s3]=res%mod;
}

int main(){
	cin >> n;
	cout << dfs(0,"TTT") << endl;
	return 0;
}

### Prompt

Please formulate 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<iostream>
#include<map>
using namespace std;
const int mod=1000000007;
int n;
map<string,long> dp[101];

bool ok(string s){
	for(int i=0;i<4;i++){
		string s4=s;
		if(i!=0){
			char tmp=s4[i];
			s4[i]=s4[i-1];
			s4[i-1]=tmp;
		}
		if(s4.substr(0,3)=="AGC" || s4.substr(1)=="AGC") return false;
	}
	return true;
}

string ss="ACGT";
long dfs(int cur,string s3){
	if(dp[cur].count(s3)) return dp[cur][s3];
	if(cur==n) return 1;
	long res=0;
	for(char c:ss){
		if(ok(s3+c)) res+=dfs(cur+1,s3.substr(1)+c);
	}
	return dp[cur][s3]=res%mod;
}

int main(){
	cin >> n;
	cout << dfs(0,"TTT") << endl;
	return 0;
}

```