/*
    A=0
    G=1
    C=2
    T=3
*/
#include <bits/stdc++.h>
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define rep(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll n,dp[101][4][4][4],ans;

int main(){
    cin>>n;
    rep(i,4)rep(j,4)rep(k,4){
        if(!(i==0&&j==1&&k==2||i==0&&j==2&&k==1||i==1&&j==0&&k==2))dp[3][i][j][k]=1;
    }

    FOR(i,4,n+1)rep(j,4)rep(k,4)rep(l,4)rep(m,4){
        if(!(k==0&&l==1&&m==2||j==0&&l==1&&m==2||k==1&&l==0&&m==2||k==0&&l==2&&m==1||j==0&&k==1&&m==2))
            (dp[i][k][l][m]+=dp[i-1][j][k][l])%=mod;
    }

    rep(i,4)rep(j,4)rep(k,4)(ans+=dp[n][i][j][k])%=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
/*
    A=0
    G=1
    C=2
    T=3
*/
#include <bits/stdc++.h>
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define rep(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll n,dp[101][4][4][4],ans;

int main(){
    cin>>n;
    rep(i,4)rep(j,4)rep(k,4){
        if(!(i==0&&j==1&&k==2||i==0&&j==2&&k==1||i==1&&j==0&&k==2))dp[3][i][j][k]=1;
    }

    FOR(i,4,n+1)rep(j,4)rep(k,4)rep(l,4)rep(m,4){
        if(!(k==0&&l==1&&m==2||j==0&&l==1&&m==2||k==1&&l==0&&m==2||k==0&&l==2&&m==1||j==0&&k==1&&m==2))
            (dp[i][k][l][m]+=dp[i-1][j][k][l])%=mod;
    }

    rep(i,4)rep(j,4)rep(k,4)(ans+=dp[n][i][j][k])%=mod;
    cout<<ans<<endl;
}
```