#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
	const ll MOD = 1e9 + 7;
	const int A = 0, C = 1, G = 2, T = 3;

	int N;
	cin >> N;

	int dp[110][4][4][4] = { 0 };
	dp[0][T][T][T] = 1;
	ll res = 0;
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int k = 0; k < 4; ++k) {
				for (int l = 0; l < 4; ++l) {
					for (int m = 0; m < 4; ++m) {
						if (j == A && k == G && l == C) { continue; }
						if (j == G && k == A && l == C) { continue; }
						if (j == A && k == C && l == G) { continue; }
						if (j == A && l == G && m == C) { continue; }
						if (j == A && k == G && m == C) { continue; }

						(dp[i][j][k][l] += dp[i - 1][k][l][m]) %= MOD;
						if (i == N) {
							(res += dp[N - 1][k][l][m]) %= MOD;
						}
					}
				}
			}
		}
	}

	cout << res % MOD << 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 <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
	const ll MOD = 1e9 + 7;
	const int A = 0, C = 1, G = 2, T = 3;

	int N;
	cin >> N;

	int dp[110][4][4][4] = { 0 };
	dp[0][T][T][T] = 1;
	ll res = 0;
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int k = 0; k < 4; ++k) {
				for (int l = 0; l < 4; ++l) {
					for (int m = 0; m < 4; ++m) {
						if (j == A && k == G && l == C) { continue; }
						if (j == G && k == A && l == C) { continue; }
						if (j == A && k == C && l == G) { continue; }
						if (j == A && l == G && m == C) { continue; }
						if (j == A && k == G && m == C) { continue; }

						(dp[i][j][k][l] += dp[i - 1][k][l][m]) %= MOD;
						if (i == N) {
							(res += dp[N - 1][k][l][m]) %= MOD;
						}
					}
				}
			}
		}
	}

	cout << res % MOD << endl;

	return 0;
}

```