#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
int n;
int dpt[5][5][5][101];
// proibidos: agc, acg, gac, a*gc, ag*c
int dp(int a, int b, int c, int d) {
    if(d == n) { return 1;}
    if(dpt[a][b][c][d] != -1) return dpt[a][b][c][d];
    set<int> s = {1, 2, 3, 4};
    if((a == 1 && c == 3) || (a == 1 && b == 3) || (b == 1 && c == 3) || (b == 3 && c == 1)) {
        s.erase(2);
    }
    if (b == 1 && c == 2) {
        s.erase(3);
    }
    int r = 0;
    for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
        r = (r + dp(b, c, *it, d+1)) % 1000000007;
    }
    dpt[a][b][c][d] = r;
    return r;
}
 
int main(){
    memset(dpt, -1, sizeof dpt);
 	sc("%d", &n);
    pr("%d\n", dp(0, 0, 0, 0));
 	return 0;
}

### 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;
#define sc scanf
#define pr printf
int n;
int dpt[5][5][5][101];
// proibidos: agc, acg, gac, a*gc, ag*c
int dp(int a, int b, int c, int d) {
    if(d == n) { return 1;}
    if(dpt[a][b][c][d] != -1) return dpt[a][b][c][d];
    set<int> s = {1, 2, 3, 4};
    if((a == 1 && c == 3) || (a == 1 && b == 3) || (b == 1 && c == 3) || (b == 3 && c == 1)) {
        s.erase(2);
    }
    if (b == 1 && c == 2) {
        s.erase(3);
    }
    int r = 0;
    for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
        r = (r + dp(b, c, *it, d+1)) % 1000000007;
    }
    dpt[a][b][c][d] = r;
    return r;
}
 
int main(){
    memset(dpt, -1, sizeof dpt);
 	sc("%d", &n);
    pr("%d\n", dp(0, 0, 0, 0));
 	return 0;
}

```