#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

int main() {
    int N, MOD = 1e9 + 7;
    cin >> N;
    vector<vector<ll>> dp(N + 1, vector<ll>(64, 0));
    dp[0][63] = 1;
    rep(i, N) {
        rep(j, 64) {
            rep(k, 4) {
                if (j == 33 || j == 6 || j == 9) continue;
                int last4 = j + k * 64;
                if (last4 / 64 == 0 && last4 % 16 == 9) continue;
                if (last4 / 16 == 2 && last4 % 4 == 1) continue;
                dp[i + 1][j] += dp[i][k * 16 + j / 4];
                dp[i + 1][j] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, 64) ans = (ans + dp[N][i]) % MOD;
    cout << ans << 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 "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

int main() {
    int N, MOD = 1e9 + 7;
    cin >> N;
    vector<vector<ll>> dp(N + 1, vector<ll>(64, 0));
    dp[0][63] = 1;
    rep(i, N) {
        rep(j, 64) {
            rep(k, 4) {
                if (j == 33 || j == 6 || j == 9) continue;
                int last4 = j + k * 64;
                if (last4 / 64 == 0 && last4 % 16 == 9) continue;
                if (last4 / 16 == 2 && last4 % 4 == 1) continue;
                dp[i + 1][j] += dp[i][k * 16 + j / 4];
                dp[i + 1][j] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, 64) ans = (ans + dp[N][i]) % MOD;
    cout << ans << endl;
}
```