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

constexpr ll mod = 1000000007;

int main()
{
    int n;
    cin >> n;
    vector<vector<ll>> dp(n + 1, vector<ll>(4));
    rep(i, 4) dp[0][i] = 0, dp[1][i] = 1;
    for (int i = 1; i < n; ++i)
    {
        ll t = 0;
        rep(j, 4) t += dp[i][j];
        dp[i + 1][0] = t % mod;
        dp[i + 1][1] = (t - dp[i - 1][0] + dp[max(i - 2, 0)][1] + 10 * mod) % mod;
        dp[i + 1][2] = (t - dp[i - 1][0] - dp[i - 1][1] - 3 * dp[max(i - 2, 0)][0] + 10 * mod) % mod;
        dp[i + 1][3] = t % mod;
    }
    ll ans = 0;
    rep(i, 4) ans += dp[n][i];
    cout << ans % mod << endl;
}
### 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 <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = int64_t;
using pint = pair<int, int>;

constexpr ll mod = 1000000007;

int main()
{
    int n;
    cin >> n;
    vector<vector<ll>> dp(n + 1, vector<ll>(4));
    rep(i, 4) dp[0][i] = 0, dp[1][i] = 1;
    for (int i = 1; i < n; ++i)
    {
        ll t = 0;
        rep(j, 4) t += dp[i][j];
        dp[i + 1][0] = t % mod;
        dp[i + 1][1] = (t - dp[i - 1][0] + dp[max(i - 2, 0)][1] + 10 * mod) % mod;
        dp[i + 1][2] = (t - dp[i - 1][0] - dp[i - 1][1] - 3 * dp[max(i - 2, 0)][0] + 10 * mod) % mod;
        dp[i + 1][3] = t % mod;
    }
    ll ans = 0;
    rep(i, 4) ans += dp[n][i];
    cout << ans % mod << endl;
}
```