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

int dp[101][4][4][4];

int main(){
  int N;
  cin >> N;
  
  dp[0][3][3][3] = 1; //上からi桁目まで見たときその前の三桁の状態
  //A->0 G->1 C->2 T->3

  rep(l,N){
    rep(i,4){
      rep(j,4){
        rep(k,4){
          if(dp[l][i][j][k] == 0)continue;
          rep(a,4){
            if(a == 2 && i == 1 && j == 0)continue; //AGC
            if(a == 2 && i == 0 && j == 1)continue; //GAC
            if(a == 1 && i == 2 && j == 0)continue; //ACG
            if(a == 2 && i == 1 && k == 0)continue; //A○GC
            if(a == 2 && j == 1 && k == 0)continue; //AG○C

            dp[l+1][a][i][j] += dp[l][i][j][k];
            dp[l+1][a][i][j] %= MOD;
          }
        }
      }
    }
  }

  int res = 0;

  rep(c1,4)rep(c2,4)rep(c3,4)res += dp[N][c1][c2][c3],res %= MOD;
  
  cout << res << endl;
  return 0;
}
### 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 <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef long long ll;
const int MOD = 1e9+7;

int dp[101][4][4][4];

int main(){
  int N;
  cin >> N;
  
  dp[0][3][3][3] = 1; //上からi桁目まで見たときその前の三桁の状態
  //A->0 G->1 C->2 T->3

  rep(l,N){
    rep(i,4){
      rep(j,4){
        rep(k,4){
          if(dp[l][i][j][k] == 0)continue;
          rep(a,4){
            if(a == 2 && i == 1 && j == 0)continue; //AGC
            if(a == 2 && i == 0 && j == 1)continue; //GAC
            if(a == 1 && i == 2 && j == 0)continue; //ACG
            if(a == 2 && i == 1 && k == 0)continue; //A○GC
            if(a == 2 && j == 1 && k == 0)continue; //AG○C

            dp[l+1][a][i][j] += dp[l][i][j][k];
            dp[l+1][a][i][j] %= MOD;
          }
        }
      }
    }
  }

  int res = 0;

  rep(c1,4)rep(c2,4)rep(c3,4)res += dp[N][c1][c2][c3],res %= MOD;
  
  cout << res << endl;
  return 0;
}
```