#include <iostream>
#define A 1
#define G 2
#define C 3
#define T 4

typedef long long ll;

const int MOD = 1e9 + 7;
const int N_MAX = 105;
const int AGCT[] = {A, G, C, T};

using namespace std;

ll memo[N_MAX][5][5][5][5] = {0};
int N;

ll dfs(int i, int c1, int c2, int c3, int c4) {
    if (c2 == A && c3 == G && c4 == C) return 0;
    if (c2 == A && c3 == C && c4 == G) return 0;
    if (c2 == G && c3 == A && c4 == C) return 0;
    if (c1 == A && c3 == G && c4 == C) return 0;
    if (c1 == A && c2 == G && c4 == C) return 0;
    if (i == N) return 1;

    if (memo[i][c1][c2][c3][c4] > 0) {
        return memo[i][c1][c2][c3][c4];
    }

    for (auto c : AGCT) {
        memo[i][c1][c2][c3][c4] =
            (memo[i][c1][c2][c3][c4] + dfs(i + 1, c2, c3, c4, c)) % MOD;
    }

    return memo[i][c1][c2][c3][c4];
}

int main() {
    cin >> N;

    cout << dfs(0, T, T, T, T) << endl;
}
### 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 <iostream>
#define A 1
#define G 2
#define C 3
#define T 4

typedef long long ll;

const int MOD = 1e9 + 7;
const int N_MAX = 105;
const int AGCT[] = {A, G, C, T};

using namespace std;

ll memo[N_MAX][5][5][5][5] = {0};
int N;

ll dfs(int i, int c1, int c2, int c3, int c4) {
    if (c2 == A && c3 == G && c4 == C) return 0;
    if (c2 == A && c3 == C && c4 == G) return 0;
    if (c2 == G && c3 == A && c4 == C) return 0;
    if (c1 == A && c3 == G && c4 == C) return 0;
    if (c1 == A && c2 == G && c4 == C) return 0;
    if (i == N) return 1;

    if (memo[i][c1][c2][c3][c4] > 0) {
        return memo[i][c1][c2][c3][c4];
    }

    for (auto c : AGCT) {
        memo[i][c1][c2][c3][c4] =
            (memo[i][c1][c2][c3][c4] + dfs(i + 1, c2, c3, c4, c)) % MOD;
    }

    return memo[i][c1][c2][c3][c4];
}

int main() {
    cin >> N;

    cout << dfs(0, T, T, T, T) << endl;
}
```