#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
//T1 C2 A3 G4
int dp[5][5][5][110];
int mod = 1000000007;
signed main() {
	int n; cin >> n;
	dp[1][1][1][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int p = 1; p <= 4; p++) {
			for (int q = 1; q <= 4; q++) {
				for (int r = 1; r <= 4; r++) {
					for (int s = 1; s <= 4; s++) {
						if (q == 3 && r == 4 && s == 2);
						else if (p == 3 && (q == 4 || r == 4) && s == 2);
						else if (q == 4 && r == 3 && s == 2);
						else if (q == 3 && r == 2 && s == 4);
						else dp[q][r][s][i] += dp[p][q][r][i - 1];
						dp[q][r][s][i] %= mod;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int p = 1; p <= 4; p++) for (int q = 1; q <= 4; q++) for (int r = 1; r <= 4; r++) {
		ans += dp[p][q][r][n]; ans %= mod;
	}
	cout << ans << endl;
}
### Prompt

In cpp, your task is to solve 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>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
//T1 C2 A3 G4
int dp[5][5][5][110];
int mod = 1000000007;
signed main() {
	int n; cin >> n;
	dp[1][1][1][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int p = 1; p <= 4; p++) {
			for (int q = 1; q <= 4; q++) {
				for (int r = 1; r <= 4; r++) {
					for (int s = 1; s <= 4; s++) {
						if (q == 3 && r == 4 && s == 2);
						else if (p == 3 && (q == 4 || r == 4) && s == 2);
						else if (q == 4 && r == 3 && s == 2);
						else if (q == 3 && r == 2 && s == 4);
						else dp[q][r][s][i] += dp[p][q][r][i - 1];
						dp[q][r][s][i] %= mod;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int p = 1; p <= 4; p++) for (int q = 1; q <= 4; q++) for (int r = 1; r <= 4; r++) {
		ans += dp[p][q][r][n]; ans %= mod;
	}
	cout << ans << endl;
}
```