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

int dp[101][4][4][4];

int mod = 1e9+7;

int main(){
	int n;
	cin>>n;
	dp[0][3][3][3] = 1;
	for(int len = 0; len <= n; len++){
		for(int c1 = 0; c1 < 4; c1++){
			for(int c2 = 0; c2 < 4; c2++){
				for(int c3 = 0; c3 < 4; c3++){
					if(dp[len][c1][c2][c3]==0) continue;
					for(int a = 0; a < 4; a++){
						if(a==2 && c1==1 && c2==0) continue;
						if(a==2 && c1==0 && c2==1) continue;
						if(a==1 && c1==2 && c2==0) continue;
						if(a==2 && c1==1 && c3==0) continue;
						if(a==2 && c2==1 && c3==0) continue;

						dp[len+1][a][c1][c2]+=dp[len][c1][c2][c3];
						dp[len+1][a][c1][c2]%=mod;

					}
				}
			}
		}
	}

	int res = 0;
	for(int c1=0;c1<4;c1++){
		for(int c2=0;c2<4;c2++){
			for(int c3=0; c3<4; c3++){
				res+=dp[n][c1][c2][c3];
				res%=mod; 
			}
		}
	}
	cout<<res;
}
### 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>
using namespace std;

int dp[101][4][4][4];

int mod = 1e9+7;

int main(){
	int n;
	cin>>n;
	dp[0][3][3][3] = 1;
	for(int len = 0; len <= n; len++){
		for(int c1 = 0; c1 < 4; c1++){
			for(int c2 = 0; c2 < 4; c2++){
				for(int c3 = 0; c3 < 4; c3++){
					if(dp[len][c1][c2][c3]==0) continue;
					for(int a = 0; a < 4; a++){
						if(a==2 && c1==1 && c2==0) continue;
						if(a==2 && c1==0 && c2==1) continue;
						if(a==1 && c1==2 && c2==0) continue;
						if(a==2 && c1==1 && c3==0) continue;
						if(a==2 && c2==1 && c3==0) continue;

						dp[len+1][a][c1][c2]+=dp[len][c1][c2][c3];
						dp[len+1][a][c1][c2]%=mod;

					}
				}
			}
		}
	}

	int res = 0;
	for(int c1=0;c1<4;c1++){
		for(int c2=0;c2<4;c2++){
			for(int c3=0; c3<4; c3++){
				res+=dp[n][c1][c2][c3];
				res%=mod; 
			}
		}
	}
	cout<<res;
}
```