#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;

map<tuple<int, char, char, char>, long long> dp;

long long dfs(int n, char b1, char b2, char b3)
{
	if (n == 0) return 1;
	auto status = make_tuple(n, b1, b2, b3);
	if (dp.count(status)) return dp[status];
	static string str = "ACGT";
	long long res = 0;
	for(auto&& c : str)
	{
		if(c == 'C')
		{
			if (b1 == 'G' && (b2 == 'A' || b3 == 'A')) continue;
			if (b1 == 'A' && b2 == 'G') continue;
			if (b3 == 'A' && b2 == 'G') continue;
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
		else if(c == 'G')
		{
			if (b1 == 'C' && b2 == 'A') continue;
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
		else
		{
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
	}
	return dp[status] = res;
}

int main()
{
	int n;
	cin >> n;
	cout << dfs(n, 'D', 'D', 'D') << "\n";
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;

const int INF = 1e9 + 7;

map<tuple<int, char, char, char>, long long> dp;

long long dfs(int n, char b1, char b2, char b3)
{
	if (n == 0) return 1;
	auto status = make_tuple(n, b1, b2, b3);
	if (dp.count(status)) return dp[status];
	static string str = "ACGT";
	long long res = 0;
	for(auto&& c : str)
	{
		if(c == 'C')
		{
			if (b1 == 'G' && (b2 == 'A' || b3 == 'A')) continue;
			if (b1 == 'A' && b2 == 'G') continue;
			if (b3 == 'A' && b2 == 'G') continue;
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
		else if(c == 'G')
		{
			if (b1 == 'C' && b2 == 'A') continue;
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
		else
		{
			res += dfs(n - 1, c, b1, b2);
			res %= INF;
		}
	}
	return dp[status] = res;
}

int main()
{
	int n;
	cin >> n;
	cout << dfs(n, 'D', 'D', 'D') << "\n";
}

```