#include<bits/stdc++.h>
using namespace std;
const long mod=1e9+7;
long N,dp[111][6][6][6][6];
long find(int now,int back1,int back2,int back3,int back4){
  if(dp[now][back1][back2][back3][back4]!=-1){
    return dp[now][back1][back2][back3][back4];
  }
  if(back1 == 0 && back2 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back1 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 2 && back4 == 1){
    return 0;
  }
  if(back2 == 1 && back3 == 0 && back4 == 2){
    return 0;
  }
  if(now==N){
    return 1;
  }
  long ans=0;
  for(int i=0;i<4;i++){
    ans+=find(now+1,back2,back3,back4,i);
  }
  return dp[now][back1][back2][back3][back4]=ans%mod;
}

int main(){
  cin>>N;
  memset(dp,-1,sizeof(dp));
  cout<<find(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,dp[111][6][6][6][6];
long find(int now,int back1,int back2,int back3,int back4){
  if(dp[now][back1][back2][back3][back4]!=-1){
    return dp[now][back1][back2][back3][back4];
  }
  if(back1 == 0 && back2 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back1 == 0 && back3 == 1 && back4 == 2){
    return 0;
  }
  if(back2 == 0 && back3 == 2 && back4 == 1){
    return 0;
  }
  if(back2 == 1 && back3 == 0 && back4 == 2){
    return 0;
  }
  if(now==N){
    return 1;
  }
  long ans=0;
  for(int i=0;i<4;i++){
    ans+=find(now+1,back2,back3,back4,i);
  }
  return dp[now][back1][back2][back3][back4]=ans%mod;
}

int main(){
  cin>>N;
  memset(dp,-1,sizeof(dp));
  cout<<find(0,4,4,4,4)<<endl;
}

```