#include <iostream>
using namespace std;
#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < (N); ++i)
int main()
{
  int N;
  cin >> N;
  int A = 0;
  int C = 1;
  int G = 2;
  long dp[101][5][5][5] = {};
  dp[0][4][4][4] = 1;
  REP(i, N)
  REP(j, 5)
  REP(k, 5)
  REP(l, 5)
  REP(m, 4)
  {
    if (k == A && l == G && m == C)
      continue;
    if (k == A && l == C && m == G)
      continue;
    if (k == G && l == A && m == C)
      continue;
    if (j == A && l == G && m == C)
      continue;
    if (j == A && k == G && m == C)
      continue;
    dp[i + 1][k][l][m] += dp[i][j][k][l];
    dp[i + 1][k][l][m] %= MOD;
  }

  long 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

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 <iostream>
using namespace std;
#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < (N); ++i)
int main()
{
  int N;
  cin >> N;
  int A = 0;
  int C = 1;
  int G = 2;
  long dp[101][5][5][5] = {};
  dp[0][4][4][4] = 1;
  REP(i, N)
  REP(j, 5)
  REP(k, 5)
  REP(l, 5)
  REP(m, 4)
  {
    if (k == A && l == G && m == C)
      continue;
    if (k == A && l == C && m == G)
      continue;
    if (k == G && l == A && m == C)
      continue;
    if (j == A && l == G && m == C)
      continue;
    if (j == A && k == G && m == C)
      continue;
    dp[i + 1][k][l][m] += dp[i][j][k][l];
    dp[i + 1][k][l][m] %= MOD;
  }

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