#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;

ll const MOD=1e9+7;

int main(){
    ll n;cin>>n;
    ll an=0;
    ll dp[110][4][4][4];
    rep(i,0,4)rep(j,0,4)rep(k,0,4)dp[3][i][j][k]=1;
    dp[3][0][2][1]=0;
    dp[3][0][1][2]=0;
    dp[3][2][0][1]=0;
    for(int i=4;i<=n;i++){
        rep(j,0,4){
            rep(k,0,4){
                rep(l,0,4){
                    rep(m,0,4){
                        if((m==0&&k==2&&l==1)||(m==0&&j==2&&l==1)||(j==0&&k==2&&l==1)||(j==0&&k==1&&l==2)||(j==2&&k==0&&l==1))continue;
                        dp[i][j][k][l]+=dp[i-1][m][j][k];
                        dp[i][j][k][l]%=MOD;
                    }
                }
            }
        }
    }
    rep(i,0,4)rep(j,0,4)rep(k,0,4){an+=dp[n][i][j][k];an%=MOD;}
    cout<<an<<endl;
}

    








### Prompt

Construct a CPP code solution to the problem outlined:

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;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;

ll const MOD=1e9+7;

int main(){
    ll n;cin>>n;
    ll an=0;
    ll dp[110][4][4][4];
    rep(i,0,4)rep(j,0,4)rep(k,0,4)dp[3][i][j][k]=1;
    dp[3][0][2][1]=0;
    dp[3][0][1][2]=0;
    dp[3][2][0][1]=0;
    for(int i=4;i<=n;i++){
        rep(j,0,4){
            rep(k,0,4){
                rep(l,0,4){
                    rep(m,0,4){
                        if((m==0&&k==2&&l==1)||(m==0&&j==2&&l==1)||(j==0&&k==2&&l==1)||(j==0&&k==1&&l==2)||(j==2&&k==0&&l==1))continue;
                        dp[i][j][k][l]+=dp[i-1][m][j][k];
                        dp[i][j][k][l]%=MOD;
                    }
                }
            }
        }
    }
    rep(i,0,4)rep(j,0,4)rep(k,0,4){an+=dp[n][i][j][k];an%=MOD;}
    cout<<an<<endl;
}

    








```