#include<bits/stdc++.h>
using namespace std;
const long mod=1e9+7;
long N,memo[111][6][6][6][6];
long rec(int now,int c1,int c2,int c3,int c4){
  // printf("%d %d %d %d %d\n",now,c1,c2,c3,c4);
  if(memo[now][c1][c2][c3][c4]!=-1)return memo[now][c1][c2][c3][c4];
  if(c1==0&&c2==1&&c4==2)return 0;
  if(c1==0&&c3==1&&c4==2)return 0;
  if(c2==0&&c3==1&&c4==2)return 0;
  if(c2==0&&c3==2&&c4==1)return 0;
  if(c2==1&&c3==0&&c4==2)return 0;
  if(now==N)return 1;
  long ans=0;
  for(int i=0;i<4;i++)ans+=rec(now+1,c2,c3,c4,i);
  return memo[now][c1][c2][c3][c4]=ans%mod;
}
int main(){
  cin>>N;
  memset(memo,-1,sizeof(memo));
  cout<<rec(0,4,4,4,4)<<endl;
}

### 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 long mod=1e9+7;
long N,memo[111][6][6][6][6];
long rec(int now,int c1,int c2,int c3,int c4){
  // printf("%d %d %d %d %d\n",now,c1,c2,c3,c4);
  if(memo[now][c1][c2][c3][c4]!=-1)return memo[now][c1][c2][c3][c4];
  if(c1==0&&c2==1&&c4==2)return 0;
  if(c1==0&&c3==1&&c4==2)return 0;
  if(c2==0&&c3==1&&c4==2)return 0;
  if(c2==0&&c3==2&&c4==1)return 0;
  if(c2==1&&c3==0&&c4==2)return 0;
  if(now==N)return 1;
  long ans=0;
  for(int i=0;i<4;i++)ans+=rec(now+1,c2,c3,c4,i);
  return memo[now][c1][c2][c3][c4]=ans%mod;
}
int main(){
  cin>>N;
  memset(memo,-1,sizeof(memo));
  cout<<rec(0,4,4,4,4)<<endl;
}

```