#include <bits/stdc++.h>

constexpr int64_t MOD = 1e9 + 7;

using namespace std;

bool is_agc(string& str) {
	if(str.find("AGC") != string::npos) return true;
	for(int i = 0; i < str.length() - 1; i++) {
		string tmp = str;
		swap(tmp[i], tmp[i+1]);
		if(tmp.find("AGC") != string::npos) return true;
	}
	
	return false;
}

int main() {
	int n;
	cin >> n;
	
	vector<map<string,int>> dp(n+1, map<string,int>());
	
	dp[0]["TTT"] = 1;
	
	for(int i = 0; i < n; i++) {
		for(auto& last : dp[i]) {
			for(char c : {'A', 'C', 'G', 'T'}) {
				string test = last.first + c;
				if(!is_agc(test))(dp[i+1][test.substr(1,3)] += last.second) %= MOD;
			}
		}
	}
	
	int sum = 0;
	
	for(auto& last : dp[n]) {
		(sum += last.second) %= MOD;
	}
	
	cout << sum;

	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>

constexpr int64_t MOD = 1e9 + 7;

using namespace std;

bool is_agc(string& str) {
	if(str.find("AGC") != string::npos) return true;
	for(int i = 0; i < str.length() - 1; i++) {
		string tmp = str;
		swap(tmp[i], tmp[i+1]);
		if(tmp.find("AGC") != string::npos) return true;
	}
	
	return false;
}

int main() {
	int n;
	cin >> n;
	
	vector<map<string,int>> dp(n+1, map<string,int>());
	
	dp[0]["TTT"] = 1;
	
	for(int i = 0; i < n; i++) {
		for(auto& last : dp[i]) {
			for(char c : {'A', 'C', 'G', 'T'}) {
				string test = last.first + c;
				if(!is_agc(test))(dp[i+1][test.substr(1,3)] += last.second) %= MOD;
			}
		}
	}
	
	int sum = 0;
	
	for(auto& last : dp[n]) {
		(sum += last.second) %= MOD;
	}
	
	cout << sum;

	return 0;
}
```