#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i)

signed main() {
    ll N;
    cin >> N;
    ll DP[N + 1][4][4][4], res = 0;
    rep(i, N + 1) rep(j, 4) rep(k, 4) rep(l, 4) DP[i][j][k][l] = 0;
    DP[0][3][3][3] = 1;
    rep(i, N) {
        rep(j, 4) rep(k, 4) rep(l, 4) rep(m, 4) {
            if (j == 0 && k == 1 && m == 2) continue;
            if (j == 0 && l == 1 && m == 2) continue;
            if (k == 0 && l == 1 && m == 2) continue;
            if (k == 0 && l == 2 && m == 1) continue;
            if (k == 1 && l == 0 && m == 2) continue;
            DP[i + 1][k][l][m] += DP[i][j][k][l];
            DP[i + 1][k][l][m] %= MOD;
        }
    }
    rep(i, 4) rep(j, 4) rep(k, 4) res += DP[N][i][j][k];
    cout << res % MOD << endl;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i)

signed main() {
    ll N;
    cin >> N;
    ll DP[N + 1][4][4][4], res = 0;
    rep(i, N + 1) rep(j, 4) rep(k, 4) rep(l, 4) DP[i][j][k][l] = 0;
    DP[0][3][3][3] = 1;
    rep(i, N) {
        rep(j, 4) rep(k, 4) rep(l, 4) rep(m, 4) {
            if (j == 0 && k == 1 && m == 2) continue;
            if (j == 0 && l == 1 && m == 2) continue;
            if (k == 0 && l == 1 && m == 2) continue;
            if (k == 0 && l == 2 && m == 1) continue;
            if (k == 1 && l == 0 && m == 2) continue;
            DP[i + 1][k][l][m] += DP[i][j][k][l];
            DP[i + 1][k][l][m] %= MOD;
        }
    }
    rep(i, 4) rep(j, 4) rep(k, 4) res += DP[N][i][j][k];
    cout << res % MOD << endl;
}
```