#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll mod = 1000000000 + 7;
ll dp[111][625];
bool ng[625];

int f(int a, int b, int c, int d) {
  return a * 125 + b * 25 + c * 5 + d;
}
// a:1, g:2, c:3, t:4

int main() {
  ll N;
  cin >> N;
  dp[0][0] = 1;

  for (int i = 0; i < 5; ++i) {
    ng[f(i, 1, 2, 3)] = true;
    ng[f(1, i, 2, 3)] = true;
    ng[f(1, 2, i, 3)] = true;
    ng[f(i, 2, 1, 3)] = true;
    ng[f(i, 1, 3, 2)] = true;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 625; ++j) {
      if (dp[i][j]) {
        for (int k = 1; k < 5; ++k) {
          int next = (j * 5 % 625) + k;
          if (ng[next])
            continue;
          dp[i + 1][next] += dp[i][j];
          dp[i + 1][next] %= mod;
        }
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i < 625; ++i) {
    ans += dp[N][i];
  }
  ans %= mod;
  cout << ans << endl;
}

### Prompt

Please formulate 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;
const ll mod = 1000000000 + 7;
ll dp[111][625];
bool ng[625];

int f(int a, int b, int c, int d) {
  return a * 125 + b * 25 + c * 5 + d;
}
// a:1, g:2, c:3, t:4

int main() {
  ll N;
  cin >> N;
  dp[0][0] = 1;

  for (int i = 0; i < 5; ++i) {
    ng[f(i, 1, 2, 3)] = true;
    ng[f(1, i, 2, 3)] = true;
    ng[f(1, 2, i, 3)] = true;
    ng[f(i, 2, 1, 3)] = true;
    ng[f(i, 1, 3, 2)] = true;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 625; ++j) {
      if (dp[i][j]) {
        for (int k = 1; k < 5; ++k) {
          int next = (j * 5 % 625) + k;
          if (ng[next])
            continue;
          dp[i + 1][next] += dp[i][j];
          dp[i + 1][next] %= mod;
        }
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i < 625; ++i) {
    ans += dp[N][i];
  }
  ans %= mod;
  cout << ans << endl;
}

```