#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll LINF = ll(1e18);

const ll MOD = ll(1e9+7);

int main(){
  int n;cin>>n;
  vector<vector<ll>> dp(n+1, vector<ll>(64, 0LL));
  rep(i, 64)dp[3][i]=1LL;
  dp[3][6]=dp[3][9]=dp[3][18]=0LL;
  repb(i, 3, n){
  	rep(j, 64){
      dp[i][j]%=MOD;
      int c1=j>>2, c2=j%16;
      rep(k, 4){
        if(k==1 && c2==2)continue;
        if(k==2 && (c2==1 || c2==4 || c1==1 || (j%4==1 && j/16==0)))continue;
      	dp[i+1][c2*4+k]+=dp[i][j];
      }
    }
  }
  ll ans=0LL;
  rep(i, 64)ans+=dp[n][i]%MOD;
  cout<<ans%MOD<<endl;
}

### Prompt

Your challenge is to write a cpp solution 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<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
#include<cstdlib>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;
const ll LINF = ll(1e18);

const ll MOD = ll(1e9+7);

int main(){
  int n;cin>>n;
  vector<vector<ll>> dp(n+1, vector<ll>(64, 0LL));
  rep(i, 64)dp[3][i]=1LL;
  dp[3][6]=dp[3][9]=dp[3][18]=0LL;
  repb(i, 3, n){
  	rep(j, 64){
      dp[i][j]%=MOD;
      int c1=j>>2, c2=j%16;
      rep(k, 4){
        if(k==1 && c2==2)continue;
        if(k==2 && (c2==1 || c2==4 || c1==1 || (j%4==1 && j/16==0)))continue;
      	dp[i+1][c2*4+k]+=dp[i][j];
      }
    }
  }
  ll ans=0LL;
  rep(i, 64)ans+=dp[n][i]%MOD;
  cout<<ans%MOD<<endl;
}

```