#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;

const int mod = 1e9+7;

int dp[110][4][4][4];

int main(){
  int n;
  cin >> n;
  dp[0][3][3][3] = 1;
  rep(d,n) {
    rep(i,4) {
      rep(j,4) {
        rep(k,4) {
          if (dp[d][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[d+1][a][i][j] += dp[d][i][j][k]) %= mod;
          }
        }
      }
    }
  }
  int res = 0;
  rep(i,4) rep(j,4) rep(k,4) (res += dp[n][i][j][k]) %= mod;
  cout << res << endl;
  return 0;
} 
### 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;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;

const int mod = 1e9+7;

int dp[110][4][4][4];

int main(){
  int n;
  cin >> n;
  dp[0][3][3][3] = 1;
  rep(d,n) {
    rep(i,4) {
      rep(j,4) {
        rep(k,4) {
          if (dp[d][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[d+1][a][i][j] += dp[d][i][j][k]) %= mod;
          }
        }
      }
    }
  }
  int res = 0;
  rep(i,4) rep(j,4) rep(k,4) (res += dp[n][i][j][k]) %= mod;
  cout << res << endl;
  return 0;
} 
```