#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int A = 0;
const int C = 1;
const int G = 2;
// const int T = 3;

int main(){
    
    int n;
    cin >> n;
	
	ll dp[n+1][4][4][4]; // 末尾ijkかつ条件を満たすもの
	memset(dp,0,sizeof(dp));
	rep(i,4) rep(j,4) rep(k,4) dp[3][i][j][k] = 1;
	dp[3][A][G][C] = 0;
	dp[3][A][C][G] = 0;
	dp[3][G][A][C] = 0;
	
	for(int i = 4; i < n+1; i++){
		rep(c1,4) rep(c2,4) rep(c3,4) rep(c4,4){
			if((c1==A && c2 == G && c4 == C) ||
			   (c1==A && c3 == G && c4 == C)) continue;
			dp[i][c2][c3][c4] += dp[i-1][c1][c2][c3];
			dp[i][c2][c3][c4] %= MOD;
		}
		dp[i][A][G][C] = 0;
		dp[i][A][C][G] = 0;
		dp[i][G][A][C] = 0;
	}
	
	ll res = 0;
	rep(i,4) rep(j,4) rep(k,4) res += dp[n][i][j][k]; res %= MOD;
	cout << res << endl;
    return 0;
    
}

### Prompt

Develop a solution in CPP to the problem described below:

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 rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int A = 0;
const int C = 1;
const int G = 2;
// const int T = 3;

int main(){
    
    int n;
    cin >> n;
	
	ll dp[n+1][4][4][4]; // 末尾ijkかつ条件を満たすもの
	memset(dp,0,sizeof(dp));
	rep(i,4) rep(j,4) rep(k,4) dp[3][i][j][k] = 1;
	dp[3][A][G][C] = 0;
	dp[3][A][C][G] = 0;
	dp[3][G][A][C] = 0;
	
	for(int i = 4; i < n+1; i++){
		rep(c1,4) rep(c2,4) rep(c3,4) rep(c4,4){
			if((c1==A && c2 == G && c4 == C) ||
			   (c1==A && c3 == G && c4 == C)) continue;
			dp[i][c2][c3][c4] += dp[i-1][c1][c2][c3];
			dp[i][c2][c3][c4] %= MOD;
		}
		dp[i][A][G][C] = 0;
		dp[i][A][C][G] = 0;
		dp[i][G][A][C] = 0;
	}
	
	ll res = 0;
	rep(i,4) rep(j,4) rep(k,4) res += dp[n][i][j][k]; res %= MOD;
	cout << res << endl;
    return 0;
    
}

```