#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long ans;
map<int,map<string, long long > > dp;
int n;
string maap[4] = {"A","T","G","C"};

bool cek(string x){
	if(x.find("AGC")!=string::npos) return 0;
	for(int i =0;i<3;i++){
		swap(x[i],x[i+1]);
		if(x.find("AGC")!=string::npos) return 0;
		swap(x[i],x[i+1]);
	}
	return 1;
}

long long dfs(int pos, string las){
	if(pos==n) return 1;
	if(dp[pos][las]!=0) return dp[pos][las];
	
	string st = las;
	st.erase(0,1);
	
	long long ret = 0;
	
	for(int i =0;i<4;i++){
		if(cek(las+maap[i])) ret = (ret+dfs(pos+1,st + maap[i] ) )%MOD;
	}
	
	return dp[pos][las] = ret;
}

int main(){
	scanf("%d",&n);
	ans = dfs(0,"TTT");
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please create a solution in cpp 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>
#define MOD 1000000007
using namespace std;

long long ans;
map<int,map<string, long long > > dp;
int n;
string maap[4] = {"A","T","G","C"};

bool cek(string x){
	if(x.find("AGC")!=string::npos) return 0;
	for(int i =0;i<3;i++){
		swap(x[i],x[i+1]);
		if(x.find("AGC")!=string::npos) return 0;
		swap(x[i],x[i+1]);
	}
	return 1;
}

long long dfs(int pos, string las){
	if(pos==n) return 1;
	if(dp[pos][las]!=0) return dp[pos][las];
	
	string st = las;
	st.erase(0,1);
	
	long long ret = 0;
	
	for(int i =0;i<4;i++){
		if(cek(las+maap[i])) ret = (ret+dfs(pos+1,st + maap[i] ) )%MOD;
	}
	
	return dp[pos][las] = ret;
}

int main(){
	scanf("%d",&n);
	ans = dfs(0,"TTT");
	printf("%lld\n",ans);
	return 0;
}
```