#include <iostream>
#include <string>
#define llint long long
#define mod 1000000007

using namespace std;

int n;
llint dp[105][4][4][4];

int main(void)
{
	cin >> n;
	dp[0][3][3][3] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 4; j++){
			for(int k = 0; k < 4; k++){
				for(int l = 0; l < 4; l++){
					for(int m = 0; m < 4; m++){
						if(k == 0 && l == 1 && m == 2) continue;
						if(k == 1 && l == 0 && m == 2) continue;
						if(k == 0 && l == 2 && m == 1) continue;
						if(j == 0 && k == 1 && m == 2) continue;
						if(j == 0 && l == 1 && m == 2) continue;
						dp[i+1][k][l][m] += dp[i][j][k][l];
						dp[i+1][k][l][m] %= mod;
					}
				}
			}
		}
	}
	llint ans = 0;
	for(int j = 0; j < 4; j++){
		for(int k = 0; k < 4; k++){
			for(int l = 0; l < 4; l++){
				ans += dp[n][j][k][l];
				ans %= mod;
			}
		}
	}
	cout << ans <<endl;
	
	return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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>
#define llint long long
#define mod 1000000007

using namespace std;

int n;
llint dp[105][4][4][4];

int main(void)
{
	cin >> n;
	dp[0][3][3][3] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 4; j++){
			for(int k = 0; k < 4; k++){
				for(int l = 0; l < 4; l++){
					for(int m = 0; m < 4; m++){
						if(k == 0 && l == 1 && m == 2) continue;
						if(k == 1 && l == 0 && m == 2) continue;
						if(k == 0 && l == 2 && m == 1) continue;
						if(j == 0 && k == 1 && m == 2) continue;
						if(j == 0 && l == 1 && m == 2) continue;
						dp[i+1][k][l][m] += dp[i][j][k][l];
						dp[i+1][k][l][m] %= mod;
					}
				}
			}
		}
	}
	llint ans = 0;
	for(int j = 0; j < 4; j++){
		for(int k = 0; k < 4; k++){
			for(int l = 0; l < 4; l++){
				ans += dp[n][j][k][l];
				ans %= mod;
			}
		}
	}
	cout << ans <<endl;
	
	return 0;
}
```