#include<iostream>

#define MOD (long(1e9) + 7)

using namespace std;

int main(){
    int N;
    cin >> N;
    
    long dp[N+1][64];
    for(int i=0; i<N+1; i++){
        for(int j=0; j<64; j++){
            dp[i][j] = 0;
        }
    }
    for(int i=0; i<4; i++){
        dp[1][i] = 1;
    }
    
    for(int i=1; i<N; i++){
        for(int j=0; j<64; j++){
            bool c = ((j%4 == 1) & (j/4%4 == 2)) | ((j%4 == 2) & (j/4/4%4 == 1)) | ((j/4%4 == 2) & (j/4/4%4 == 1)) | ((j%4 == 2) & (j/4%4 == 1));
            bool g = (j%4 == 3) & (j/4%4 == 1);
            
            for(int k=0; k<4; k++){
                if(c && k==3) continue;
                else if(g && k==2) continue;
                dp[i+1][j*4%64 + k] += dp[i][j];
                dp[i+1][j*4%64 + k] %= MOD;
            }
        }
    }
    long ans = 0;
    for(int i=0; i<64; i++){
        ans += dp[N][i];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
### Prompt

Please provide a CPP coded solution 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<iostream>

#define MOD (long(1e9) + 7)

using namespace std;

int main(){
    int N;
    cin >> N;
    
    long dp[N+1][64];
    for(int i=0; i<N+1; i++){
        for(int j=0; j<64; j++){
            dp[i][j] = 0;
        }
    }
    for(int i=0; i<4; i++){
        dp[1][i] = 1;
    }
    
    for(int i=1; i<N; i++){
        for(int j=0; j<64; j++){
            bool c = ((j%4 == 1) & (j/4%4 == 2)) | ((j%4 == 2) & (j/4/4%4 == 1)) | ((j/4%4 == 2) & (j/4/4%4 == 1)) | ((j%4 == 2) & (j/4%4 == 1));
            bool g = (j%4 == 3) & (j/4%4 == 1);
            
            for(int k=0; k<4; k++){
                if(c && k==3) continue;
                else if(g && k==2) continue;
                dp[i+1][j*4%64 + k] += dp[i][j];
                dp[i+1][j*4%64 + k] %= MOD;
            }
        }
    }
    long ans = 0;
    for(int i=0; i<64; i++){
        ans += dp[N][i];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
```