#include <bits/stdc++.h>
using namespace std;
int m = 1e9+7;

int main() {
	int n; cin>>n;
	vector<map<string,int>> dp(101);
	vector<string> disallowed = {"AGC","GAC","ACG","AGGC","AGTC","ATGC"};
	string s = "ACGT";

	dp[0]["XXXX"] = 1;
	for (int i=0; i<100; i++) {
		for (pair<string,int> p: dp[i]) {
			for (char c : s) {
				string last4 = p.first.substr(1,3) + c;
				string last3 = last4.substr(1,3);
				bool skip = false;
				for (string x : disallowed) {
					if (x==last4 or x==last3) {
						skip = true;
						break;
					}
				}
				if (skip) continue;
				dp[i+1][last4] = (dp[i+1][last4]%m + p.second%m)%m;
			}
		}
	}

	int ans=0;
	for (pair<string, int> p : dp[n])
		ans = (ans%m + p.second%m)%m;
	cout << ans << endl;
	
	return 0;
}

### 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 m = 1e9+7;

int main() {
	int n; cin>>n;
	vector<map<string,int>> dp(101);
	vector<string> disallowed = {"AGC","GAC","ACG","AGGC","AGTC","ATGC"};
	string s = "ACGT";

	dp[0]["XXXX"] = 1;
	for (int i=0; i<100; i++) {
		for (pair<string,int> p: dp[i]) {
			for (char c : s) {
				string last4 = p.first.substr(1,3) + c;
				string last3 = last4.substr(1,3);
				bool skip = false;
				for (string x : disallowed) {
					if (x==last4 or x==last3) {
						skip = true;
						break;
					}
				}
				if (skip) continue;
				dp[i+1][last4] = (dp[i+1][last4]%m + p.second%m)%m;
			}
		}
	}

	int ans=0;
	for (pair<string, int> p : dp[n])
		ans = (ans%m + p.second%m)%m;
	cout << ans << endl;
	
	return 0;
}

```