#include <bits/stdc++.h>
using namespace std;
const int sz=105;
int n;
char a[5]={'A', 'C', 'G','T','s'};
long long dp[sz][5][5][5];
long long m=1e9+7;
long long add(long long a,long long b){return (a%m+b%m)%m;}

/*
AGC
GAC
ACG
*/

long long solve(int idx,int p1=4,int p2=4,int p3=4){
    long long &ret=dp[idx][p1][p2][p3];
    if(~ret) return ret;
    if(!idx) return ret=1;
    ret=0;
    for(int i=0;i<4;i++){
        if(a[i]=='A'&&a[p1]=='G'&&a[p2]=='C') continue;
        if(a[i]=='G'&&a[p1]=='A'&&a[p2]=='C') continue;
        if(a[i]=='A'&&a[p1]=='C'&&a[p2]=='G') continue;
        if(a[i]=='A'&&a[p2]=='G'&&a[p3]=='C') continue;
        if(a[i]=='A'&&a[p1]=='G'&&a[p3]=='C') continue;
        ret=add(ret,solve(idx-1,i,p1,p2));
    }
    return ret;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    printf("%lld",solve(n));
    return 0;
}

### Prompt

Please create a solution in CPP 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;
const int sz=105;
int n;
char a[5]={'A', 'C', 'G','T','s'};
long long dp[sz][5][5][5];
long long m=1e9+7;
long long add(long long a,long long b){return (a%m+b%m)%m;}

/*
AGC
GAC
ACG
*/

long long solve(int idx,int p1=4,int p2=4,int p3=4){
    long long &ret=dp[idx][p1][p2][p3];
    if(~ret) return ret;
    if(!idx) return ret=1;
    ret=0;
    for(int i=0;i<4;i++){
        if(a[i]=='A'&&a[p1]=='G'&&a[p2]=='C') continue;
        if(a[i]=='G'&&a[p1]=='A'&&a[p2]=='C') continue;
        if(a[i]=='A'&&a[p1]=='C'&&a[p2]=='G') continue;
        if(a[i]=='A'&&a[p2]=='G'&&a[p3]=='C') continue;
        if(a[i]=='A'&&a[p1]=='G'&&a[p3]=='C') continue;
        ret=add(ret,solve(idx-1,i,p1,p2));
    }
    return ret;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    printf("%lld",solve(n));
    return 0;
}

```