#include <iostream>
using namespace std;
typedef long long ll;
ll dp[64][101], M=1e9+7;
ll f(int x, int y){
    if(y==0)return 1;
    if(dp[x][y]!=-1)return dp[x][y];
    int a=(x/16)%4, b=(x/4)%4, c=x%4;
    ll r=f(b*16+c*4, y-1);
    r += f(b*16+c*4+3, y-1);
    r%=M;
    if(b!=0||c!=1)r+=f(b*16+c*4+2, y-1);
    r%=M;
    if(!(b==0&&c==2)&&
       !(b==2&&c==0)&&
       !(a==0&&b==2)&&
       !(a==0&&c==2)
    ){
        r += f(b*16+c*4+1, y-1);
        r%=M;
    }
    return dp[x][y]=r;
}
int main() {
    int n;
    cin >> n;
    for(int i=0;i<64;i++){
        for(int j=0;j<101;j++){
            dp[i][j] = -1;
        }
    }
    cout << f(63, n) << endl;
	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 <iostream>
using namespace std;
typedef long long ll;
ll dp[64][101], M=1e9+7;
ll f(int x, int y){
    if(y==0)return 1;
    if(dp[x][y]!=-1)return dp[x][y];
    int a=(x/16)%4, b=(x/4)%4, c=x%4;
    ll r=f(b*16+c*4, y-1);
    r += f(b*16+c*4+3, y-1);
    r%=M;
    if(b!=0||c!=1)r+=f(b*16+c*4+2, y-1);
    r%=M;
    if(!(b==0&&c==2)&&
       !(b==2&&c==0)&&
       !(a==0&&b==2)&&
       !(a==0&&c==2)
    ){
        r += f(b*16+c*4+1, y-1);
        r%=M;
    }
    return dp[x][y]=r;
}
int main() {
    int n;
    cin >> n;
    for(int i=0;i<64;i++){
        for(int j=0;j<101;j++){
            dp[i][j] = -1;
        }
    }
    cout << f(63, n) << endl;
	return 0;
}
```