#include<iostream>
using namespace std;
#define int long long
#define rep(i,N) for(int(i)=0;(i)<(N);(i)++)

const int MOD = 1e9+7;
signed main(){
    int N;
    cin >> N;
    
    int dp[110][4][4][4];
    int A=0, G=1, C=2, T=3;

    rep(a,4)rep(b,4)rep(c,4) dp[3][a][b][c] = 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;i++){
        rep(a,4)rep(b,4)rep(c,4)rep(d,4){
            if(b == A && c == G && d == C) continue;
            if(b == A && c == C && d == G) continue;
            if(b == G && c == A && d == C) continue;
            if(a == A && c == G && d == C) continue;
            if(a == A && b == G && d == C) continue;
            (dp[i][b][c][d] += dp[i-1][a][b][c]) %= MOD;
        }
    }

    int ans = 0;
    rep(a,4)rep(b,4)rep(c,4){
        (ans += dp[N][a][b][c]) %= MOD;
    }

    cout << ans << endl;
}
### 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>
using namespace std;
#define int long long
#define rep(i,N) for(int(i)=0;(i)<(N);(i)++)

const int MOD = 1e9+7;
signed main(){
    int N;
    cin >> N;
    
    int dp[110][4][4][4];
    int A=0, G=1, C=2, T=3;

    rep(a,4)rep(b,4)rep(c,4) dp[3][a][b][c] = 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;i++){
        rep(a,4)rep(b,4)rep(c,4)rep(d,4){
            if(b == A && c == G && d == C) continue;
            if(b == A && c == C && d == G) continue;
            if(b == G && c == A && d == C) continue;
            if(a == A && c == G && d == C) continue;
            if(a == A && b == G && d == C) continue;
            (dp[i][b][c][d] += dp[i-1][a][b][c]) %= MOD;
        }
    }

    int ans = 0;
    rep(a,4)rep(b,4)rep(c,4){
        (ans += dp[N][a][b][c]) %= MOD;
    }

    cout << ans << endl;
}
```