#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
map<string, ll> dp[101];
int main() {
	int N;
	cin >> N;
	dp[0][""] = 1;
	char ch[5] = "ACGT";
	for (int i = 0; i < N; i++) {
		for (auto p : dp[i]) {
			for (int j = 0; j < 4; j++) {
				string t = p.first + string(1, ch[j]);
				if (t.size() > 4) t.erase(t.begin());
				if (t.find("AGC") != string::npos || t.find("GAC") != string::npos || t.find("ACG") != string::npos) continue;
				if (t.size() <= 3) {
					(dp[i + 1][t] += p.second) %= MOD;
					continue;
				}
				if (t[0] == 'A'&&t[2] == 'G'&&t[3] == 'C') continue;
				if (t[0] == 'A'&&t[1] == 'G'&&t[3] == 'C') continue;
				(dp[i + 1][t] += p.second) %= MOD;
			}
		}
	}
	ll ans = 0;
	for (auto p : dp[N]) {
		(ans += p.second) %= MOD;
	}
	cout << ans << 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;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
map<string, ll> dp[101];
int main() {
	int N;
	cin >> N;
	dp[0][""] = 1;
	char ch[5] = "ACGT";
	for (int i = 0; i < N; i++) {
		for (auto p : dp[i]) {
			for (int j = 0; j < 4; j++) {
				string t = p.first + string(1, ch[j]);
				if (t.size() > 4) t.erase(t.begin());
				if (t.find("AGC") != string::npos || t.find("GAC") != string::npos || t.find("ACG") != string::npos) continue;
				if (t.size() <= 3) {
					(dp[i + 1][t] += p.second) %= MOD;
					continue;
				}
				if (t[0] == 'A'&&t[2] == 'G'&&t[3] == 'C') continue;
				if (t[0] == 'A'&&t[1] == 'G'&&t[3] == 'C') continue;
				(dp[i + 1][t] += p.second) %= MOD;
			}
		}
	}
	ll ans = 0;
	for (auto p : dp[N]) {
		(ans += p.second) %= MOD;
	}
	cout << ans << endl;
}

```