#include<bits/stdc++.h>
using namespace std;
int dp[101][4][4][4];
int main(){
int N;
int MOD = 1000000000+7;
scanf("%d",&N);
dp[0][3][3][3] = 1;

for(int len=0;len<N;len++){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				if(dp[len][i][j][k]==0) continue;
				
				for(int a=0;a<4;a++){
					if(a==2&&i==1&&j==0) continue;	
					if(a==1&&i==2&&j==0) continue;	
					if(a==2&&i==0&&j==1) continue;	
					if(a==2&&i==1&&k==0) continue;	
					if(a==2&&j==1&&k==0) continue;	
					
					dp[len+1][a][i][j]+=dp[len][i][j][k];
					dp[len+1][a][i][j]%=MOD;
				}
			}
		}
	}
}

int ans = 0;
for(int i=0;i<4;i++){
	for(int j=0;j<4;j++){
		for(int k=0;k<4;k++){
			ans+=dp[N][i][j][k];
			ans%=MOD;
		}
	}
}

printf("%d\n",ans);
}
### Prompt

Please formulate 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;
int dp[101][4][4][4];
int main(){
int N;
int MOD = 1000000000+7;
scanf("%d",&N);
dp[0][3][3][3] = 1;

for(int len=0;len<N;len++){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				if(dp[len][i][j][k]==0) continue;
				
				for(int a=0;a<4;a++){
					if(a==2&&i==1&&j==0) continue;	
					if(a==1&&i==2&&j==0) continue;	
					if(a==2&&i==0&&j==1) continue;	
					if(a==2&&i==1&&k==0) continue;	
					if(a==2&&j==1&&k==0) continue;	
					
					dp[len+1][a][i][j]+=dp[len][i][j][k];
					dp[len+1][a][i][j]%=MOD;
				}
			}
		}
	}
}

int ans = 0;
for(int i=0;i<4;i++){
	for(int j=0;j<4;j++){
		for(int k=0;k<4;k++){
			ans+=dp[N][i][j][k];
			ans%=MOD;
		}
	}
}

printf("%d\n",ans);
}
```