#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = ((int) a); i < ((int) n); i++)
using namespace std;

const int MOD = 1000000007;

enum { A, C, G, T };
int dp[101][4][4][4];

int main(void) {
  int N;
  cin >> N;

  REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) {
    if (i == A && j == G && k == C) continue;
    if (i == A && j == C && k == G) continue;
    if (i == G && j == A && k == C) continue;
    dp[3][i][j][k] = 1;
  }

  REP(t, 3, N) REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) REP(l, 0, 4) {
    if (j == A && k == G && l == C) continue;
    if (j == A && k == C && l == G) continue;
    if (j == G && k == A && l == C) continue;

    if (i == A && k == G && l == C) continue;
    if (i == A && j == G && l == C) continue;

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

  int ans = 0;
  REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) {
    ans += dp[N][i][j][k];
    ans %= MOD;
  }
  cout << ans << endl;
}
### Prompt

Generate 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>
#define REP(i, a, n) for (int i = ((int) a); i < ((int) n); i++)
using namespace std;

const int MOD = 1000000007;

enum { A, C, G, T };
int dp[101][4][4][4];

int main(void) {
  int N;
  cin >> N;

  REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) {
    if (i == A && j == G && k == C) continue;
    if (i == A && j == C && k == G) continue;
    if (i == G && j == A && k == C) continue;
    dp[3][i][j][k] = 1;
  }

  REP(t, 3, N) REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) REP(l, 0, 4) {
    if (j == A && k == G && l == C) continue;
    if (j == A && k == C && l == G) continue;
    if (j == G && k == A && l == C) continue;

    if (i == A && k == G && l == C) continue;
    if (i == A && j == G && l == C) continue;

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

  int ans = 0;
  REP(i, 0, 4) REP(j, 0, 4) REP(k, 0, 4) {
    ans += dp[N][i][j][k];
    ans %= MOD;
  }
  cout << ans << endl;
}
```