#include<iostream>
#include<algorithm>

using namespace std;

#define MOD 1000000007

char cl[5] = {'x','A','C','G','T'};

int n;
int dp[5][5][5][101];

int f(char c, char a, char b, int d){
	if(d==n)return 1;
	if(dp[c][a][b][d]!=-1)return dp[c][a][b][d];
	int sum = 0;
	for(int i = 1;i < 5;i++){
		if(cl[a] == 'A' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[a] == 'A' && cl[b] == 'C' && cl[i] == 'G')continue;
		if(cl[a] == 'G' && cl[b] == 'A' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'G' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'T' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'G' && cl[b] == 'T' && cl[i] == 'C')continue;
		sum += f(a, b, i, d+1);
		sum %= MOD;
	}
	return dp[c][a][b][d] = sum;
}

int main(){
	cin >> n;
	fill_n(***dp,5*5*5*101,-1);
	cout << f(0, 0, 0, 0) << 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<iostream>
#include<algorithm>

using namespace std;

#define MOD 1000000007

char cl[5] = {'x','A','C','G','T'};

int n;
int dp[5][5][5][101];

int f(char c, char a, char b, int d){
	if(d==n)return 1;
	if(dp[c][a][b][d]!=-1)return dp[c][a][b][d];
	int sum = 0;
	for(int i = 1;i < 5;i++){
		if(cl[a] == 'A' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[a] == 'A' && cl[b] == 'C' && cl[i] == 'G')continue;
		if(cl[a] == 'G' && cl[b] == 'A' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'G' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'T' && cl[b] == 'G' && cl[i] == 'C')continue;
		if(cl[c] == 'A' && cl[a] == 'G' && cl[b] == 'T' && cl[i] == 'C')continue;
		sum += f(a, b, i, d+1);
		sum %= MOD;
	}
	return dp[c][a][b][d] = sum;
}

int main(){
	cin >> n;
	fill_n(***dp,5*5*5*101,-1);
	cout << f(0, 0, 0, 0) << endl;

	return 0;
}
```