#include <cstdio>
#include <vector>
#include <numeric>

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main() {
    ll n;
    scanf("%lld", &n);
    vector< vector<ll> > dp(n + 1, vector<ll>(1 << 6, 0));
    // dp.at(i).at(j) = number of different string satisfying the condition with its length of i, and the last three letters are represented by j. (T = 0, G = 1, C = 2, A = 3).
    dp.at(0).at(0) = 1;
    for (ll i = 0; i < n; ++i) for (ll j = 0; j < (1 << 6); ++j) for (ll k = 0; k < 4; ++k) {
        ll f = ((j & 15) << 2) + k;
        if (f == 0b110110 || f == 0b011110 || f == 0b111001 || ((j & (3 << 4)) == 3 << 4 && k == 2 && ((j & (3 << 2)) == (1 << 2) || (j & 3) == 1))) continue;
        dp.at(i + 1).at(((j & 15) << 2) + k) += dp.at(i).at(j);
        dp.at(i + 1).at(((j & 15) << 2) + k) %= MOD;
    }
    printf("%lld\n", accumulate(dp.back().begin(), dp.back().end(), 0LL) % MOD);
    return 0;
}

### Prompt

Develop a solution in Cpp 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 <cstdio>
#include <vector>
#include <numeric>

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main() {
    ll n;
    scanf("%lld", &n);
    vector< vector<ll> > dp(n + 1, vector<ll>(1 << 6, 0));
    // dp.at(i).at(j) = number of different string satisfying the condition with its length of i, and the last three letters are represented by j. (T = 0, G = 1, C = 2, A = 3).
    dp.at(0).at(0) = 1;
    for (ll i = 0; i < n; ++i) for (ll j = 0; j < (1 << 6); ++j) for (ll k = 0; k < 4; ++k) {
        ll f = ((j & 15) << 2) + k;
        if (f == 0b110110 || f == 0b011110 || f == 0b111001 || ((j & (3 << 4)) == 3 << 4 && k == 2 && ((j & (3 << 2)) == (1 << 2) || (j & 3) == 1))) continue;
        dp.at(i + 1).at(((j & 15) << 2) + k) += dp.at(i).at(j);
        dp.at(i + 1).at(((j & 15) << 2) + k) %= MOD;
    }
    printf("%lld\n", accumulate(dp.back().begin(), dp.back().end(), 0LL) % MOD);
    return 0;
}

```