#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <numeric>

using namespace std;

using ll = long long;

ll mod = 1000000007;

int n;

map<pair<int, string>, ll> memo;

ll dfs(int i, string s) {
    if (i == n) {
        return 1;
    }

    auto cur = make_pair(i, s);

    if (memo.count(cur)) {
        return memo[cur];
    }

    ll ret = 0;

    string t = s.substr(1);
    ret = (ret + dfs(i + 1, t + 'A')) % mod;
    ret = (ret + dfs(i + 1, t + 'T')) % mod;

    if (t != "AC") {
        ret = (ret + dfs(i + 1, t + 'G')) % mod;
    }

    if (t != "AG" && t != "GA" && !(s[0] == 'A' && s[1] == 'G') && !(s[0] == 'A' && s[2] == 'G')) {
        ret = (ret + dfs(i + 1, t + 'C')) % mod;
    }

    return memo[cur] = ret;
}

int main() {
    cin >> n;

    cout << dfs(0, "TTT") << 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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <numeric>

using namespace std;

using ll = long long;

ll mod = 1000000007;

int n;

map<pair<int, string>, ll> memo;

ll dfs(int i, string s) {
    if (i == n) {
        return 1;
    }

    auto cur = make_pair(i, s);

    if (memo.count(cur)) {
        return memo[cur];
    }

    ll ret = 0;

    string t = s.substr(1);
    ret = (ret + dfs(i + 1, t + 'A')) % mod;
    ret = (ret + dfs(i + 1, t + 'T')) % mod;

    if (t != "AC") {
        ret = (ret + dfs(i + 1, t + 'G')) % mod;
    }

    if (t != "AG" && t != "GA" && !(s[0] == 'A' && s[1] == 'G') && !(s[0] == 'A' && s[2] == 'G')) {
        ret = (ret + dfs(i + 1, t + 'C')) % mod;
    }

    return memo[cur] = ret;
}

int main() {
    cin >> n;

    cout << dfs(0, "TTT") << endl;
}

```