#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

const int mod=1e9+7;
int dp[101][5][5][5];

signed main()
{
    int N; cin>>N;

    dp[0][4][4][4]=1;
    for(int i=0;i<N;i++){ 
        REP(x,5) REP(y,5) REP(z,5) REP(j,4){
            if(y==0 and z==1 and j==2) continue;
            if(y==0 and z==2 and j==1) continue;
            if(y==1 and z==0 and j==2) continue;

            if(x==0 and y==1 and j==2) continue;
            if(x==0 and z==1 and j==2) continue;

            dp[i+1][y][z][j]+=dp[i][x][y][z];
            dp[i+1][y][z][j]%=mod;
        }
    }
    int ans=0;
    REP(x,4) REP(y,4) REP(z,4) ans=(ans+dp[N][x][y][z])%mod;
    cout<<ans<<endl;
}

### 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>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

const int mod=1e9+7;
int dp[101][5][5][5];

signed main()
{
    int N; cin>>N;

    dp[0][4][4][4]=1;
    for(int i=0;i<N;i++){ 
        REP(x,5) REP(y,5) REP(z,5) REP(j,4){
            if(y==0 and z==1 and j==2) continue;
            if(y==0 and z==2 and j==1) continue;
            if(y==1 and z==0 and j==2) continue;

            if(x==0 and y==1 and j==2) continue;
            if(x==0 and z==1 and j==2) continue;

            dp[i+1][y][z][j]+=dp[i][x][y][z];
            dp[i+1][y][z][j]%=mod;
        }
    }
    int ans=0;
    REP(x,4) REP(y,4) REP(z,4) ans=(ans+dp[N][x][y][z])%mod;
    cout<<ans<<endl;
}

```