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

const int md = (1.0e+9) + 7;
vector<int> vec(101, -1);
vector<int> vecg(101, -1);

long long calc(int N);
long long calcg(int N);

long long calc(int N) {
	if (N < 0) return 0;
	if (vec[N] != -1) return vec[N];

	long long ans;
	ans = 4 * calc(N - 1) - 2 * calc(N - 3) - 3 * calc(N - 4) - calcg(N - 2) + calcg(N - 3);

	while (ans < 0) ans += md;
	ans %= md;
	vec[N] = ans;
	return ans;
}

long long calcg(int N) {
	if (N < 0) return 0;
	if (vecg[N] != -1) return vecg[N];

	long long ans;
	ans = calc(N - 1) - calc(N - 3) + calcg(N - 3);

	while (ans < 0) ans += md;
	ans %= md;
	vecg[N] = ans;
	return ans;
}

int main()
{
	int N;
	cin >> N;

	vec[0] = 1;
	vecg[0] = 0;

	cout << calc(N) << endl;
}
### 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;

const int md = (1.0e+9) + 7;
vector<int> vec(101, -1);
vector<int> vecg(101, -1);

long long calc(int N);
long long calcg(int N);

long long calc(int N) {
	if (N < 0) return 0;
	if (vec[N] != -1) return vec[N];

	long long ans;
	ans = 4 * calc(N - 1) - 2 * calc(N - 3) - 3 * calc(N - 4) - calcg(N - 2) + calcg(N - 3);

	while (ans < 0) ans += md;
	ans %= md;
	vec[N] = ans;
	return ans;
}

long long calcg(int N) {
	if (N < 0) return 0;
	if (vecg[N] != -1) return vecg[N];

	long long ans;
	ans = calc(N - 1) - calc(N - 3) + calcg(N - 3);

	while (ans < 0) ans += md;
	ans %= md;
	vecg[N] = ans;
	return ans;
}

int main()
{
	int N;
	cin >> N;

	vec[0] = 1;
	vecg[0] = 0;

	cout << calc(N) << endl;
}
```