#include<iostream>
#include<vector>
using namespace std;
int p = 1000000007;
int N_MAX = 101;
int main()
{
  int n;
  cin >> n;
  long long a[N_MAX][19];
  long long *pi,*pm;
  long long res=0;
  fill(a[2],a[2]+16,1);
  fill(a[2]+16,a[2]+19,0);
  for(int i=3;i<=n;i++){
    pi=a[i];
    pm=a[i-1];
    pi[0]=pi[2]=pi[3]=(pm[0]+pm[4]+pm[8]+pm[12])%p;
    pi[4]=pi[5]=pi[7]=(pm[1]+pm[5]+pm[9]+pm[13])%p;
    pi[8]=(pm[2]+pm[6]+pm[10]+pm[14]+pm[16]+pm[17])%p;
    pi[12]=pi[15]=(pm[3]+pm[7]+pm[11]+pm[15]+pm[18])%p;
    pi[1]=(pm[0]+pm[4]+pm[12])%p;
    pi[6]=(pm[5]+pm[9]+pm[13])%p;
    pi[9]=(pm[6]+pm[10]+pm[14])%p;
    pi[10]=pi[11]=(pm[6]+pm[10]+pm[14]+pm[16]+pm[17])%p;
    pi[13]=(pm[3]+pm[7]+pm[11]+pm[15])%p;
    pi[14]=(pm[7]+pm[11]+pm[15]+pm[18])%p;
    pi[16]=pi[18]=pm[2];
    pi[17]=pm[3];
  }
  for(int i=0;i<19;i++){
    res+=a[n][i];
    res=res%p;
  }
  cout << res << endl;
  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<iostream>
#include<vector>
using namespace std;
int p = 1000000007;
int N_MAX = 101;
int main()
{
  int n;
  cin >> n;
  long long a[N_MAX][19];
  long long *pi,*pm;
  long long res=0;
  fill(a[2],a[2]+16,1);
  fill(a[2]+16,a[2]+19,0);
  for(int i=3;i<=n;i++){
    pi=a[i];
    pm=a[i-1];
    pi[0]=pi[2]=pi[3]=(pm[0]+pm[4]+pm[8]+pm[12])%p;
    pi[4]=pi[5]=pi[7]=(pm[1]+pm[5]+pm[9]+pm[13])%p;
    pi[8]=(pm[2]+pm[6]+pm[10]+pm[14]+pm[16]+pm[17])%p;
    pi[12]=pi[15]=(pm[3]+pm[7]+pm[11]+pm[15]+pm[18])%p;
    pi[1]=(pm[0]+pm[4]+pm[12])%p;
    pi[6]=(pm[5]+pm[9]+pm[13])%p;
    pi[9]=(pm[6]+pm[10]+pm[14])%p;
    pi[10]=pi[11]=(pm[6]+pm[10]+pm[14]+pm[16]+pm[17])%p;
    pi[13]=(pm[3]+pm[7]+pm[11]+pm[15])%p;
    pi[14]=(pm[7]+pm[11]+pm[15]+pm[18])%p;
    pi[16]=pi[18]=pm[2];
    pi[17]=pm[3];
  }
  for(int i=0;i<19;i++){
    res+=a[n][i];
    res=res%p;
  }
  cout << res << endl;
  return 0;
}
```