#include <iostream>
#include <cstring>

using namespace std;

const int z = 1e9+7;

int main() {
    int n;
    cin >> n;

    int dp[n-2][64];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < 64; i++) {
        dp[0][i] = i == 6 || i == 9 || i == 33 ? 0 : 1;
    }
    for (int i = 1; i < n - 2; i++) {
        for (int j = 0; j < 256; j++) {
            if (j % 64 == 6 || j % 64 == 9 || j % 64 == 33
                    || (j & 207) == 9 || (j & 243) == 33) {
                continue;
            }
            dp[i][j%64] = (dp[i][j%64] + dp[i-1][j/4]) % z;
        }
    }

    int ans = 0;
    for (int i = 0; i < 64; i++) {
        ans = (ans + dp[n-3][i]) % z;
    }

    cout << ans << endl;

    return 0;
}

### Prompt

Please create a solution in cpp 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 <cstring>

using namespace std;

const int z = 1e9+7;

int main() {
    int n;
    cin >> n;

    int dp[n-2][64];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < 64; i++) {
        dp[0][i] = i == 6 || i == 9 || i == 33 ? 0 : 1;
    }
    for (int i = 1; i < n - 2; i++) {
        for (int j = 0; j < 256; j++) {
            if (j % 64 == 6 || j % 64 == 9 || j % 64 == 33
                    || (j & 207) == 9 || (j & 243) == 33) {
                continue;
            }
            dp[i][j%64] = (dp[i][j%64] + dp[i-1][j/4]) % z;
        }
    }

    int ans = 0;
    for (int i = 0; i < 64; i++) {
        ans = (ans + dp[n-3][i]) % z;
    }

    cout << ans << endl;

    return 0;
}

```