#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n;
int dp[110][5][5][5];

int rek(int pos, int x, int y, int z) {
	if (pos == n) return 1;

	int &ret = dp[pos][x][y][z];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i ++) {
		if (y == 0 && z == 1 && i == 2) continue;
		if (y == 1 && z == 0 && i == 2) continue;
		if (y == 0 && z == 2 && i == 1) continue;
		if (x == 0 && z == 1 && i == 2) continue;
		if (x == 0 && y == 1 && i == 2) continue;
		ret += rek(pos+1, y, z, i);
		ret %= MOD;
	}

	return ret;
}

int main () {

	cin >> n;
	memset(dp, -1, sizeof dp);
	cout << rek(0, 4, 4, 4);

	return 0;
}
### Prompt

Develop a solution in cpp 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>
#define X first
#define Y second
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n;
int dp[110][5][5][5];

int rek(int pos, int x, int y, int z) {
	if (pos == n) return 1;

	int &ret = dp[pos][x][y][z];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i ++) {
		if (y == 0 && z == 1 && i == 2) continue;
		if (y == 1 && z == 0 && i == 2) continue;
		if (y == 0 && z == 2 && i == 1) continue;
		if (x == 0 && z == 1 && i == 2) continue;
		if (x == 0 && y == 1 && i == 2) continue;
		ret += rek(pos+1, y, z, i);
		ret %= MOD;
	}

	return ret;
}

int main () {

	cin >> n;
	memset(dp, -1, sizeof dp);
	cout << rek(0, 4, 4, 4);

	return 0;
}
```