#include <bits/stdc++.h>


#define ll long long
#define scan(x) scanf("%lld",&x)

const ll mod=1e9+7;

using namespace std;

ll dp[101][5][5][5],n;

ll func(ll x, ll prev1, ll prev2 , ll prev3)
{
    if(x>=n)
        return 1;
    ll &ret= dp[x][prev1][prev2][prev3];
    if(ret!=-1)
        return ret;
    ll ans=0;
    for(ll i=1;i<=4;i++)
    {
        if(i==2)
        {
            if((prev1==3)&&(prev2==1))
                continue;

        }
        if(i==3)
        {
            if((prev1==2)&&(prev2==1))
                continue;
             if((prev1==1)&&(prev2==2))
                continue;

            if((prev2==2)&&(prev3==1))
                continue;

            if((prev3==1)&&(prev1==2))
                continue;

        }

        ans+= func(x+1,i,prev1,prev2)%mod;
        ans%=mod;


    }
    return ret=ans;

}


int main()
{
    memset(dp,-1,sizeof dp);
    ll i,j,k,l,m;
    cin >> n;
    cout << func(0,0,0,0);
}

### Prompt

Generate 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 ll long long
#define scan(x) scanf("%lld",&x)

const ll mod=1e9+7;

using namespace std;

ll dp[101][5][5][5],n;

ll func(ll x, ll prev1, ll prev2 , ll prev3)
{
    if(x>=n)
        return 1;
    ll &ret= dp[x][prev1][prev2][prev3];
    if(ret!=-1)
        return ret;
    ll ans=0;
    for(ll i=1;i<=4;i++)
    {
        if(i==2)
        {
            if((prev1==3)&&(prev2==1))
                continue;

        }
        if(i==3)
        {
            if((prev1==2)&&(prev2==1))
                continue;
             if((prev1==1)&&(prev2==2))
                continue;

            if((prev2==2)&&(prev3==1))
                continue;

            if((prev3==1)&&(prev1==2))
                continue;

        }

        ans+= func(x+1,i,prev1,prev2)%mod;
        ans%=mod;


    }
    return ret=ans;

}


int main()
{
    memset(dp,-1,sizeof dp);
    ll i,j,k,l,m;
    cin >> n;
    cout << func(0,0,0,0);
}

```