#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std ;

typedef long long LL ;
const int P=1e9+7;

map<string,int>v[200] ;
int n ;

inline int ok ( string s )
{
    int i ;
    for ( i=0 ; i<=3 ; i++ ) 
    {
        string t=s ;
        if ( i>=1 ) swap(t[i-1],t[i]);
        if ( t.find("AGC")!=t.npos ) return 0 ;
    }
    return 1 ;
}

inline int dfs ( int x , string s )
{
    // puts(s.c_str());
    if ( v[x].count(s)>=1 ) return v[x][s];
    if ( x==n ) return 1 ;
    int res=0 ;
    if ( ok(s+'A') ) res=(res+dfs(x+1,s.substr(1)+'A'))%P;
    if ( ok(s+'C') ) res=(res+dfs(x+1,s.substr(1)+'C'))%P;
    if ( ok(s+'G') ) res=(res+dfs(x+1,s.substr(1)+'G'))%P;
    if ( ok(s+'T') ) res=(res+dfs(x+1,s.substr(1)+'T'))%P;
    v[x][s]=res;
    return res ;
}

int main ()
{
    scanf("%d",&n);
    printf("%d\n",dfs(0,"TTT"));
    return 0 ;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <algorithm>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std ;

typedef long long LL ;
const int P=1e9+7;

map<string,int>v[200] ;
int n ;

inline int ok ( string s )
{
    int i ;
    for ( i=0 ; i<=3 ; i++ ) 
    {
        string t=s ;
        if ( i>=1 ) swap(t[i-1],t[i]);
        if ( t.find("AGC")!=t.npos ) return 0 ;
    }
    return 1 ;
}

inline int dfs ( int x , string s )
{
    // puts(s.c_str());
    if ( v[x].count(s)>=1 ) return v[x][s];
    if ( x==n ) return 1 ;
    int res=0 ;
    if ( ok(s+'A') ) res=(res+dfs(x+1,s.substr(1)+'A'))%P;
    if ( ok(s+'C') ) res=(res+dfs(x+1,s.substr(1)+'C'))%P;
    if ( ok(s+'G') ) res=(res+dfs(x+1,s.substr(1)+'G'))%P;
    if ( ok(s+'T') ) res=(res+dfs(x+1,s.substr(1)+'T'))%P;
    v[x][s]=res;
    return res ;
}

int main ()
{
    scanf("%d",&n);
    printf("%d\n",dfs(0,"TTT"));
    return 0 ;
}
```