#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n;
  cin>>n;
  ll dp[n+1][64];
  rep(i,0,n+1){
    rep(j,0,64){
      dp[i][j]=0;
    }
  }
  dp[0][63]=1;
  rep(i,0,n){
    rep(j,0,64){
      int p=j%4;
      int q=j/4%4;
      int r=j/16%4;
      if(p==0 && q==1 && r==2) continue;
      if(p==1 && q==0 && r==2) continue;
      if(p==0 && q==2 && r==1) continue;
      rep(k,0,4){
        if(p==0 && q==1 && k==2) continue;
        if(q==0 && r==1 && k==2) continue;
        if(q==1 && r==0 && k==2) continue;
        if(q==0 && r==2 && k==1) continue;
        if(p==0 && r==1 && k==2) continue;
        dp[i+1][q+r*4+k*16]+=dp[i][j];
        dp[i+1][q+r*4+k*16]%=mod;
      }
    }
  }
  ll ans=0;
  rep(i,0,64){
    ans+=dp[n][i];
    ans%=mod;
  }
  cout<<ans<<endl;
}
### Prompt

Create a solution in cpp for 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;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n;
  cin>>n;
  ll dp[n+1][64];
  rep(i,0,n+1){
    rep(j,0,64){
      dp[i][j]=0;
    }
  }
  dp[0][63]=1;
  rep(i,0,n){
    rep(j,0,64){
      int p=j%4;
      int q=j/4%4;
      int r=j/16%4;
      if(p==0 && q==1 && r==2) continue;
      if(p==1 && q==0 && r==2) continue;
      if(p==0 && q==2 && r==1) continue;
      rep(k,0,4){
        if(p==0 && q==1 && k==2) continue;
        if(q==0 && r==1 && k==2) continue;
        if(q==1 && r==0 && k==2) continue;
        if(q==0 && r==2 && k==1) continue;
        if(p==0 && r==1 && k==2) continue;
        dp[i+1][q+r*4+k*16]+=dp[i][j];
        dp[i+1][q+r*4+k*16]%=mod;
      }
    }
  }
  ll ans=0;
  rep(i,0,64){
    ans+=dp[n][i];
    ans%=mod;
  }
  cout<<ans<<endl;
}
```