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

int n;
int dp[101][64];
constexpr int mod = 1e9+7;

// _AGC
// A_GC
// _GAC
// _ACG
// AG_C

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<4; ++i)
		dp[1][60+i] = 1;
	for(int i=2; i<=n; ++i){
		for(int j=0; j<4; ++j){
			for(int k=0; k<64; ++k){
				if(j == 1){
					if(k%16 == 2 || k%16 == 8) continue;
					if(k/4 == 2) continue;
					if(k/16 == 0 && k%4 == 2) continue;
				}else if(j == 2){
					if(k%16 == 1) continue;
				}
				dp[i][k%16*4+j] += dp[i-1][k];
				dp[i][k%16*4+j] %= mod;
			}
		}
	}
	int ans = 0;
	for(int i=0; i<64; ++i)
		ans = (ans + dp[n][i]) % mod;
	cout << ans << "\n";
}
### 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;

int n;
int dp[101][64];
constexpr int mod = 1e9+7;

// _AGC
// A_GC
// _GAC
// _ACG
// AG_C

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<4; ++i)
		dp[1][60+i] = 1;
	for(int i=2; i<=n; ++i){
		for(int j=0; j<4; ++j){
			for(int k=0; k<64; ++k){
				if(j == 1){
					if(k%16 == 2 || k%16 == 8) continue;
					if(k/4 == 2) continue;
					if(k/16 == 0 && k%4 == 2) continue;
				}else if(j == 2){
					if(k%16 == 1) continue;
				}
				dp[i][k%16*4+j] += dp[i-1][k];
				dp[i][k%16*4+j] %= mod;
			}
		}
	}
	int ans = 0;
	for(int i=0; i<64; ++i)
		ans = (ans + dp[n][i]) % mod;
	cout << ans << "\n";
}
```