// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef long long LL;
static const LL MOD = 1000000007;

int n;
map<string, LL> memo[102];

bool check(const string &s) {
	for (int i = 0; i < 4; ++i) {
		string t = s;
		if (i) {
			t[i - 1] = s[i];
			t[i] = s[i - 1];
		}
		if (t.find("AGC") != string::npos) {
			return false;
		}
	}
	return true;
}

LL dfs(int pos, const string &last) {
	map<string, LL> &m = memo[pos];
	if (pos == n) {
		return 1;
	}
	if (m.find(last) == m.end()) {
		LL cnt = 0;
		const string T = "AGCT";
		for (char c : T) {
			if (check(last + c)) {
				cnt = (cnt + dfs(pos + 1, last.substr(1) + c)) % MOD;
			}
		}
		m[last] = cnt;
	}
	return m[last];
}

int main(int argc, char *argv[]) {
	cin >> n;
	LL ans = dfs(0, "ZZZ");
	cout << ans << 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
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef long long LL;
static const LL MOD = 1000000007;

int n;
map<string, LL> memo[102];

bool check(const string &s) {
	for (int i = 0; i < 4; ++i) {
		string t = s;
		if (i) {
			t[i - 1] = s[i];
			t[i] = s[i - 1];
		}
		if (t.find("AGC") != string::npos) {
			return false;
		}
	}
	return true;
}

LL dfs(int pos, const string &last) {
	map<string, LL> &m = memo[pos];
	if (pos == n) {
		return 1;
	}
	if (m.find(last) == m.end()) {
		LL cnt = 0;
		const string T = "AGCT";
		for (char c : T) {
			if (check(last + c)) {
				cnt = (cnt + dfs(pos + 1, last.substr(1) + c)) % MOD;
			}
		}
		m[last] = cnt;
	}
	return m[last];
}

int main(int argc, char *argv[]) {
	cin >> n;
	LL ans = dfs(0, "ZZZ");
	cout << ans << endl;
	return 0;
}

```