#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};
ll memo[101][4][4][4];

ll dfs(int length, int a, int b, int c, int n) {
  ll ret = 0;
  if (length == n) return 1;
  if (memo[length][a][b][c]) return memo[length][a][b][c];
  REP(d, 4) {
    if (b == 0 && c == 1 && d == 2) continue;
    if (b == 1 && c == 0 && d == 2) continue;
    if (b == 0 && c == 2 && d == 1) continue;
    if (a == 0 && b == 1 && d == 2) continue;
    if (a == 0 && c == 1 && d == 2) continue;
    ret += dfs(length + 1, b, c, d, n);
  }
  return memo[length][a][b][c] = ret % MOD;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, 3, 3, 3, N) << '\n';
}

### 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, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};
ll memo[101][4][4][4];

ll dfs(int length, int a, int b, int c, int n) {
  ll ret = 0;
  if (length == n) return 1;
  if (memo[length][a][b][c]) return memo[length][a][b][c];
  REP(d, 4) {
    if (b == 0 && c == 1 && d == 2) continue;
    if (b == 1 && c == 0 && d == 2) continue;
    if (b == 0 && c == 2 && d == 1) continue;
    if (a == 0 && b == 1 && d == 2) continue;
    if (a == 0 && c == 1 && d == 2) continue;
    ret += dfs(length + 1, b, c, d, n);
  }
  return memo[length][a][b][c] = ret % MOD;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, 3, 3, 3, N) << '\n';
}

```