#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
const int mod = 1e9 + 7;
int n, dp[105][4][4][4];
//string a = "AGCT";
ll solve(int idx, int n1, int n2, int n3){
    if(idx >= n) return 1;
    if(dp[idx][n1][n2][n3] != -1) return dp[idx][n1][n2][n3];
    ll ans = 0;
    for(int i = 0; i < 4; i++){
        if((i == 1 && n2 == 0 && n3 == 2) ||
           (i == 1 && n2 == 2 && n3 == 0) ||
           (i == 2 && n2 == 0 && n3 == 1) ||
           (i == 1 && n1 == 0 && n2 == 2) ||
           (i == 1 && n1 == 0 && n3 == 2))continue;
        ans = (ans + (solve(idx + 1, n2, n3, i) % mod) ) % mod;
    }
    dp[idx][n1][n2][n3] = ans;
    return dp[idx][n1][n2][n3];
}
int main(){
    Hello
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << solve(0, 3, 3, 3);
    return 0;
}

### Prompt

Your task is to create a Cpp solution 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>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
const int mod = 1e9 + 7;
int n, dp[105][4][4][4];
//string a = "AGCT";
ll solve(int idx, int n1, int n2, int n3){
    if(idx >= n) return 1;
    if(dp[idx][n1][n2][n3] != -1) return dp[idx][n1][n2][n3];
    ll ans = 0;
    for(int i = 0; i < 4; i++){
        if((i == 1 && n2 == 0 && n3 == 2) ||
           (i == 1 && n2 == 2 && n3 == 0) ||
           (i == 2 && n2 == 0 && n3 == 1) ||
           (i == 1 && n1 == 0 && n2 == 2) ||
           (i == 1 && n1 == 0 && n3 == 2))continue;
        ans = (ans + (solve(idx + 1, n2, n3, i) % mod) ) % mod;
    }
    dp[idx][n1][n2][n3] = ans;
    return dp[idx][n1][n2][n3];
}
int main(){
    Hello
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << solve(0, 3, 3, 3);
    return 0;
}

```