#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll K=1000000007;

int main (){
    int N;
    cin>>N;
    vector<vector<ll>> X(64, vector<ll>(2, 0));
    for(int i=0; i<64; i++){
        X.at(i).push_back(1);
        
    }
    X[24][2]=0;
    X[18][2]=0;
    X[36][2]=0;
  
    for(int i=3; i<N; i++){
        for(int j=0; j<64; j++){
            X.at(j).push_back(X[(4*j)%64][i-1]+X[(4*j+1)%64][i-1]+X[(4*j+2)%64][i-1]+X[(4*j+3)%64][i-1]);
        }
        X[24][i]=0;
        X[18][i]=0;
        X[36][i]=0;
        //AG*C
        //X[22][i]-=X[24][i-1];
        X[26][i]-=X[40][i-1];
        X[30][i]-=X[56][i-1];
        //A*GC
        //X[25][i]-=X[36][i-1];
        //X[26][i]-=X[40][i-1];
        X[27][i]-=X[44][i-1];
        for(int j=0; j<64; j++){
            X[j][i] %=K;
        }
    }
    ll Sum=0;
    for(int i=0; i<64; i++){
        Sum += X[i][N-1];
        Sum %= K;
    }
    cout<<Sum;
}


### Prompt

Your challenge is to write 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>
using namespace std;
typedef long long ll;
ll K=1000000007;

int main (){
    int N;
    cin>>N;
    vector<vector<ll>> X(64, vector<ll>(2, 0));
    for(int i=0; i<64; i++){
        X.at(i).push_back(1);
        
    }
    X[24][2]=0;
    X[18][2]=0;
    X[36][2]=0;
  
    for(int i=3; i<N; i++){
        for(int j=0; j<64; j++){
            X.at(j).push_back(X[(4*j)%64][i-1]+X[(4*j+1)%64][i-1]+X[(4*j+2)%64][i-1]+X[(4*j+3)%64][i-1]);
        }
        X[24][i]=0;
        X[18][i]=0;
        X[36][i]=0;
        //AG*C
        //X[22][i]-=X[24][i-1];
        X[26][i]-=X[40][i-1];
        X[30][i]-=X[56][i-1];
        //A*GC
        //X[25][i]-=X[36][i-1];
        //X[26][i]-=X[40][i-1];
        X[27][i]-=X[44][i-1];
        for(int j=0; j<64; j++){
            X[j][i] %=K;
        }
    }
    ll Sum=0;
    for(int i=0; i<64; i++){
        Sum += X[i][N-1];
        Sum %= K;
    }
    cout<<Sum;
}


```