#include <iostream>
#include <cstring>
using namespace std;
#define A 1
#define C 2
#define G 3
#define T 4
int n;
int mem[101][5][5][5];
long MOD = 1e9+7;
long dfs(int p, int c3 ,int c2, int c1){
    if(mem[p][c3][c2][c1] != -1) return mem[p][c3][c2][c1];
    if(p == n) return 1;
    long a = 0;
    a += dfs(p+1, c2, c1, A);
    a += dfs(p+1, c2, c1, T);
    if(!(c1 == C && c2 == A))
        a += dfs(p+1, c2, c1, G);
    if(!(c1 == G && c2 == A || c1 == A && c2 == G ||
        c1 == G && c3 == A || c2 == G && c3 == A))
        a += dfs(p+1, c2, c1, C);
    a = a % MOD;
    mem[p][c3][c2][c1] = a;
    return a;
}
int main(){
    memset(mem, -1, sizeof(mem));
    cin >> n;
    cout << dfs(0, 0, 0, 0) << endl;
}
### 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 <iostream>
#include <cstring>
using namespace std;
#define A 1
#define C 2
#define G 3
#define T 4
int n;
int mem[101][5][5][5];
long MOD = 1e9+7;
long dfs(int p, int c3 ,int c2, int c1){
    if(mem[p][c3][c2][c1] != -1) return mem[p][c3][c2][c1];
    if(p == n) return 1;
    long a = 0;
    a += dfs(p+1, c2, c1, A);
    a += dfs(p+1, c2, c1, T);
    if(!(c1 == C && c2 == A))
        a += dfs(p+1, c2, c1, G);
    if(!(c1 == G && c2 == A || c1 == A && c2 == G ||
        c1 == G && c3 == A || c2 == G && c3 == A))
        a += dfs(p+1, c2, c1, C);
    a = a % MOD;
    mem[p][c3][c2][c1] = a;
    return a;
}
int main(){
    memset(mem, -1, sizeof(mem));
    cin >> n;
    cout << dfs(0, 0, 0, 0) << endl;
}
```