#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

int n;

long long memo[120][10][10][10];

long long dfs(int i, int one, int two, int three){
    if(i == n) return 1;
    if(memo[i][one][two][three] != -1) return memo[i][one][two][three];

    long long ans = 0;
    for(int f = 1;f <= 4;f++){
        if(one == 1 && two == 2 && f == 3) continue;
        if(one == 1 && three == 2 && f == 3) continue;
        if(two == 1 && three == 2 && f == 3) continue;
        if(two == 2 && three == 1 && f == 3) continue;
        if(two == 1 && three == 3 && f == 2) continue;
        ans = (ans + dfs(i+1, two, three, f)) % MOD;
    }

    return memo[i][one][two][three] = ans;
}

int main(){
    cin >> n;
    memset(memo, -1, sizeof(memo));
    cout << dfs(0, 0, 0, 0) << endl;;
    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 <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

int n;

long long memo[120][10][10][10];

long long dfs(int i, int one, int two, int three){
    if(i == n) return 1;
    if(memo[i][one][two][three] != -1) return memo[i][one][two][three];

    long long ans = 0;
    for(int f = 1;f <= 4;f++){
        if(one == 1 && two == 2 && f == 3) continue;
        if(one == 1 && three == 2 && f == 3) continue;
        if(two == 1 && three == 2 && f == 3) continue;
        if(two == 2 && three == 1 && f == 3) continue;
        if(two == 1 && three == 3 && f == 2) continue;
        ans = (ans + dfs(i+1, two, three, f)) % MOD;
    }

    return memo[i][one][two][three] = ans;
}

int main(){
    cin >> n;
    memset(memo, -1, sizeof(memo));
    cout << dfs(0, 0, 0, 0) << endl;;
    return 0;
}

```