#include <bits/stdc++.h>
using namespace std;
int dp[100][4][4][4];
int mod = 1E9+7;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	dp[0][3][3][3] = 1;
	for (int len = 0; len < N; len++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					if (dp[len][i][j][k] == 0) continue;
					for (int m = 0; m < 4; m++) {
						if (m == 2 && i == 1 && j == 0) continue;
						if (m == 2 && i == 0 && j == 1) continue;
						if (m == 1 && i == 2 && j == 0) continue;
						if (m == 2 && i == 1 && k == 0) continue;
						if (m == 2 && j == 1 && k == 0) continue;
						dp[len + 1][m][i][j] += dp[len][i][j][k];
						dp[len + 1][m][i][j] %= mod;
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				res += dp[N][i][j][k];
				res %= mod;
			}
		}
	}
	cout << res << endl;
}

### Prompt

Your task is to create 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;
int dp[100][4][4][4];
int mod = 1E9+7;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N;
	cin >> N;
	dp[0][3][3][3] = 1;
	for (int len = 0; len < N; len++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int k = 0; k < 4; k++) {
					if (dp[len][i][j][k] == 0) continue;
					for (int m = 0; m < 4; m++) {
						if (m == 2 && i == 1 && j == 0) continue;
						if (m == 2 && i == 0 && j == 1) continue;
						if (m == 1 && i == 2 && j == 0) continue;
						if (m == 2 && i == 1 && k == 0) continue;
						if (m == 2 && j == 1 && k == 0) continue;
						dp[len + 1][m][i][j] += dp[len][i][j][k];
						dp[len + 1][m][i][j] %= mod;
					}
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				res += dp[N][i][j][k];
				res %= mod;
			}
		}
	}
	cout << res << endl;
}

```