#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
using namespace std;
#define MOD 1000000007
int dp[110][5][5][5][5];




long long count(int n,int a,int b,int c,int d) {
	if (dp[n][a][b][c][d] != -1)return dp[n][a][b][c][d];

	long long temp = 0;
	

	
	if ((b==0&&c == 2 && d == 3)|| (b == 3 && c == 0 && d == 2)||(b==0&&c==3&&d==2)) {
		dp[n][a][b][c][d] = 0;
		return 0;
	}
	else if ((a == 0 && c == 3 && d == 2) || (a == 0 && b == 3 && d == 2)) {
		dp[n][a][b][c][d] = 0;
		return 0;
	}
	if (n == 1)return 1;
	for (int i = 0; i < 4; i++) {
		temp += count(n - 1, b, c, d, i);
	}

	dp[n][a][b][c][d] = temp % MOD;
	return dp[n][a][b][c][d];

	


}


int main() {
	int n;
	cin >> n;
	int ans;
	memset(dp, -1, sizeof(dp));
	ans = count(n+1, 4, 4, 4, 4);
	cout << ans;
	


	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 <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
using namespace std;
#define MOD 1000000007
int dp[110][5][5][5][5];




long long count(int n,int a,int b,int c,int d) {
	if (dp[n][a][b][c][d] != -1)return dp[n][a][b][c][d];

	long long temp = 0;
	

	
	if ((b==0&&c == 2 && d == 3)|| (b == 3 && c == 0 && d == 2)||(b==0&&c==3&&d==2)) {
		dp[n][a][b][c][d] = 0;
		return 0;
	}
	else if ((a == 0 && c == 3 && d == 2) || (a == 0 && b == 3 && d == 2)) {
		dp[n][a][b][c][d] = 0;
		return 0;
	}
	if (n == 1)return 1;
	for (int i = 0; i < 4; i++) {
		temp += count(n - 1, b, c, d, i);
	}

	dp[n][a][b][c][d] = temp % MOD;
	return dp[n][a][b][c][d];

	


}


int main() {
	int n;
	cin >> n;
	int ans;
	memset(dp, -1, sizeof(dp));
	ans = count(n+1, 4, 4, 4, 4);
	cout << ans;
	


	return 0;
}

```