#include<bits/stdc++.h>
using namespace std;
long long dp[101][5][5][5];
long long m=1000000007;

long long solve(int i,int j,int k,int l,int n)
{
    long long ans=0;
    if(dp[i][j][k][l]!=0) return dp[i][j][k][l];
    if(j==2 && k==3 && l==1) return 0;
    if(j==2 && k==1 && l==3) return 0;
    if(j==3 && k==2 && l==1) return 0;
    if(i==n) return 1;
    for(int z=1; z<=4; z++)
    {
        if(z==2 && k==3 && l==1) continue;
        if(z==2 && j==3 && l==1) continue;
        ans=(ans+solve(i+1,z,j,k,n))%m;
    }
    dp[i][j][k][l]=ans;
    return ans;
}

int main()
{
    int n;
    cin>>n;
    memset(dp,0,sizeof(dp));
    cout<<solve(0,0,0,0,n)<<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;
long long dp[101][5][5][5];
long long m=1000000007;

long long solve(int i,int j,int k,int l,int n)
{
    long long ans=0;
    if(dp[i][j][k][l]!=0) return dp[i][j][k][l];
    if(j==2 && k==3 && l==1) return 0;
    if(j==2 && k==1 && l==3) return 0;
    if(j==3 && k==2 && l==1) return 0;
    if(i==n) return 1;
    for(int z=1; z<=4; z++)
    {
        if(z==2 && k==3 && l==1) continue;
        if(z==2 && j==3 && l==1) continue;
        ans=(ans+solve(i+1,z,j,k,n))%m;
    }
    dp[i][j][k][l]=ans;
    return ans;
}

int main()
{
    int n;
    cin>>n;
    memset(dp,0,sizeof(dp));
    cout<<solve(0,0,0,0,n)<<endl;
    return 0;
}

```