#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;

int n;
string s;
long long m = 0;
int dp[101][64];

bool tes(string s4) {
	bool f = 1;
	for (int i = 0; i < 4; i++) {
		if(i > 0)
			swap(s4[i], s4[i - 1]);

		if (s4.find("AGC") != std::string::npos)
			f = 0;

		if (i > 0)
			swap(s4[i], s4[i - 1]);
	}

	return f;
}

int dfs(int t, string s3) {
	int d = 0;

	for (int i = 0; i < 3; i++) {
		if (s3[i] == 'G')
			d += 1 << (i * 2);
		if (s3[i] == 'C')
			d += 1 << (i * 2 + 1);
		if (s3[i] == 'T')
			d += 3 * (1 << (i * 2));
	}

	if (dp[t][d] > 0)
		return dp[t][d];

	if (t == n)
		return 1;

	int r = 0;
	string sd = "AGCT";

	for (int i = 0; i < 4; i++) {
		if (tes(s3 + sd[i]))
			r = (r + dfs(t + 1, s3.substr(1, 2) + sd[i])) % 1000000007;
	}

	dp[t][d] = r;
	return r;
}

int main()
{
	memset(dp, 0, sizeof(dp));

	cin >> n;

	cout << dfs(0, "TTT") << endl;

	return 0;
}
### Prompt

Create a solution in Cpp for 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 <string>
#include <algorithm>
#include <string.h>
using namespace std;

int n;
string s;
long long m = 0;
int dp[101][64];

bool tes(string s4) {
	bool f = 1;
	for (int i = 0; i < 4; i++) {
		if(i > 0)
			swap(s4[i], s4[i - 1]);

		if (s4.find("AGC") != std::string::npos)
			f = 0;

		if (i > 0)
			swap(s4[i], s4[i - 1]);
	}

	return f;
}

int dfs(int t, string s3) {
	int d = 0;

	for (int i = 0; i < 3; i++) {
		if (s3[i] == 'G')
			d += 1 << (i * 2);
		if (s3[i] == 'C')
			d += 1 << (i * 2 + 1);
		if (s3[i] == 'T')
			d += 3 * (1 << (i * 2));
	}

	if (dp[t][d] > 0)
		return dp[t][d];

	if (t == n)
		return 1;

	int r = 0;
	string sd = "AGCT";

	for (int i = 0; i < 4; i++) {
		if (tes(s3 + sd[i]))
			r = (r + dfs(t + 1, s3.substr(1, 2) + sd[i])) % 1000000007;
	}

	dp[t][d] = r;
	return r;
}

int main()
{
	memset(dp, 0, sizeof(dp));

	cin >> n;

	cout << dfs(0, "TTT") << endl;

	return 0;
}
```