#include <bits/stdc++.h>

using namespace std;
typedef long long unsigned int ll;

int dp[101][4][4][4];
int N;
int mod = 1e9 + 7;

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

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	for (int l = 0; l < 4; ++l) {
	  if (dp[i][j][k][l] == 0) continue;

	  for (int a = 0; a < 4; ++a) {
	    if (a == 2 && j == 1 && k == 0) continue;
	    if (a == 2 && j == 0 && k == 1) continue;
	    if (a == 1 && j == 2 && k == 0) continue;
	    if (a == 2 && j == 1 && l == 0) continue;
	    if (a == 2 && k == 1 && l == 0) continue;

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

	}
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	ans += dp[N][i][j][k];
	ans %= mod;
      }

    }

  }

  cout << ans << endl;
  return 0;
}


### Prompt

Please create a solution in Cpp 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;
typedef long long unsigned int ll;

int dp[101][4][4][4];
int N;
int mod = 1e9 + 7;

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

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	for (int l = 0; l < 4; ++l) {
	  if (dp[i][j][k][l] == 0) continue;

	  for (int a = 0; a < 4; ++a) {
	    if (a == 2 && j == 1 && k == 0) continue;
	    if (a == 2 && j == 0 && k == 1) continue;
	    if (a == 1 && j == 2 && k == 0) continue;
	    if (a == 2 && j == 1 && l == 0) continue;
	    if (a == 2 && k == 1 && l == 0) continue;

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

	}
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	ans += dp[N][i][j][k];
	ans %= mod;
      }

    }

  }

  cout << ans << endl;
  return 0;
}


```