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

const int maxn=103;
const int mo=1e9+7;

int n;
long long dp[maxn][256],res;

int go(int stat,int k){
	return (stat*4)%256+k;
}

bool check(int stat){
	if(stat%64==44||stat%64==56||stat%64==50) return false;
	if(stat==200||stat==216||stat==232||stat==248) return false;
	if(stat==224||stat==228||stat==232||stat==236) return false;
	return true;
}

int main(){
	scanf("%d",&n);
	dp[0][0]=1;
	for(int i=0;i<n;++i){
		for(int j=0;j<256;++j){
			if(dp[i][j]!=0&&check(j)){
//				printf("%d %d : %lld\n",i,j,dp[i][j]);
				for(int k=0;k<4;++k)
					(dp[i+1][go(j,k)]+=dp[i][j])%=mo;
			}
		}
	}
	for(int j=0;j<256;++j)
		if(check(j))
			(res+=dp[n][j])%=mo;
	printf("%lld\n",res);
	return 0;
}
### Prompt

Generate 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 maxn=103;
const int mo=1e9+7;

int n;
long long dp[maxn][256],res;

int go(int stat,int k){
	return (stat*4)%256+k;
}

bool check(int stat){
	if(stat%64==44||stat%64==56||stat%64==50) return false;
	if(stat==200||stat==216||stat==232||stat==248) return false;
	if(stat==224||stat==228||stat==232||stat==236) return false;
	return true;
}

int main(){
	scanf("%d",&n);
	dp[0][0]=1;
	for(int i=0;i<n;++i){
		for(int j=0;j<256;++j){
			if(dp[i][j]!=0&&check(j)){
//				printf("%d %d : %lld\n",i,j,dp[i][j]);
				for(int k=0;k<4;++k)
					(dp[i+1][go(j,k)]+=dp[i][j])%=mo;
			}
		}
	}
	for(int j=0;j<256;++j)
		if(check(j))
			(res+=dp[n][j])%=mo;
	printf("%lld\n",res);
	return 0;
}
```