#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

const int MOD = 1000000007;
int N;

vector<map<string, ll>> memo(N+1);
vector<string> ch = { "A", "C", "G", "T" };
vector<string> bad = { "AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC" };

bool ok(string str) {
    for (string target : bad) {
        if (str.find(target) != string::npos) return false;
    }
    return true;
}

ll dfs(int cur, string str) {
    if (memo[cur].count(str)) return memo[cur][str];
    if (cur == N) return 1;
    ll ret = 0;
    for (string c : ch) {
        if (ok(str + c)) {
            ret = (ret + dfs(cur+1, str.substr(1)+c)) % MOD;
        }
    }
    memo[cur][str] = ret;
    return ret;
}


int main() {
    cin >> N;
    rep(i, N+1) memo.push_back(map<string, ll>());
    cout << dfs(0, "TTT") << 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;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

const int MOD = 1000000007;
int N;

vector<map<string, ll>> memo(N+1);
vector<string> ch = { "A", "C", "G", "T" };
vector<string> bad = { "AGC", "ACG", "GAC", "AGGC", "ATGC", "AGTC" };

bool ok(string str) {
    for (string target : bad) {
        if (str.find(target) != string::npos) return false;
    }
    return true;
}

ll dfs(int cur, string str) {
    if (memo[cur].count(str)) return memo[cur][str];
    if (cur == N) return 1;
    ll ret = 0;
    for (string c : ch) {
        if (ok(str + c)) {
            ret = (ret + dfs(cur+1, str.substr(1)+c)) % MOD;
        }
    }
    memo[cur][str] = ret;
    return ret;
}


int main() {
    cin >> N;
    rep(i, N+1) memo.push_back(map<string, ll>());
    cout << dfs(0, "TTT") << endl;
}

```