#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

ll dp[105][4][4][4];
const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;

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

      dp[i + 1][k][l][m] += dp[i][j][k][l];
      dp[i + 1][k][l][m] %= mod;
    }
  }

  ll ans = 0;
  rep(j, 4) rep(k, 4) rep(l, 4) {
    ans += dp[n][j][k][l];
    ans %= mod;
  }
  cout << ans << 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;
using ll = long long;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

ll dp[105][4][4][4];
const int mod = 1e9 + 7;

int main() {
  int n;
  cin >> n;

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

      dp[i + 1][k][l][m] += dp[i][j][k][l];
      dp[i + 1][k][l][m] %= mod;
    }
  }

  ll ans = 0;
  rep(j, 4) rep(k, 4) rep(l, 4) {
    ans += dp[n][j][k][l];
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}

```