#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define MOD 1e9+7
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	int dp[101][4][4][4]={0};//dp[i][k][l][m]は長さiで後ろ４文字がj,k,l,mと並ぶ文字列の場合の数."TAGC"=0123とおく.
	REP(i,4){
		REP(j,4){
			REP(k,4){
				if((i==1&&j==2&&k==3)||(i==1&&j==3&&k==2)||(i==2&&j==1&&k==3)) dp[3][i][j][k]=0;
				else dp[3][i][j][k]=1;
			}
		}
	}
	for(int i=3;i<n;++i){
		REP(j,4){
			REP(k,4){
				REP(l,4){
					REP(m,4){
						if(k==1&&l==2&&m==3) continue;
						if(k==1&&l==3&&m==2) continue;
						if(k==2&&l==1&&m==3) continue;
						if(j==1&&k==2&&m==3) continue;//AG*C.
						if(j==1&&l==2&&m==3) continue;//A*GC.
						
						dp[i+1][k][l][m]+=dp[i][j][k][l];
						dp[i+1][k][l][m]%=(int)MOD;
					}
				}
			}
		}
	}
	
	llong ans=0;
	REP(i,4){
		REP(j,4){
			REP(k,4){
				ans+=dp[n][i][j][k];
				ans%=(int)MOD;
			}
		}
	}	
	
	cout<<ans<<endl;
	return 0;
}//abc122_d.復習.解答参考.
### Prompt

Please provide a CPP coded solution 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>
#define REP(i,n) for(int i=0;i<(n);++i)
#define MOD 1e9+7
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	int dp[101][4][4][4]={0};//dp[i][k][l][m]は長さiで後ろ４文字がj,k,l,mと並ぶ文字列の場合の数."TAGC"=0123とおく.
	REP(i,4){
		REP(j,4){
			REP(k,4){
				if((i==1&&j==2&&k==3)||(i==1&&j==3&&k==2)||(i==2&&j==1&&k==3)) dp[3][i][j][k]=0;
				else dp[3][i][j][k]=1;
			}
		}
	}
	for(int i=3;i<n;++i){
		REP(j,4){
			REP(k,4){
				REP(l,4){
					REP(m,4){
						if(k==1&&l==2&&m==3) continue;
						if(k==1&&l==3&&m==2) continue;
						if(k==2&&l==1&&m==3) continue;
						if(j==1&&k==2&&m==3) continue;//AG*C.
						if(j==1&&l==2&&m==3) continue;//A*GC.
						
						dp[i+1][k][l][m]+=dp[i][j][k][l];
						dp[i+1][k][l][m]%=(int)MOD;
					}
				}
			}
		}
	}
	
	llong ans=0;
	REP(i,4){
		REP(j,4){
			REP(k,4){
				ans+=dp[n][i][j][k];
				ans%=(int)MOD;
			}
		}
	}	
	
	cout<<ans<<endl;
	return 0;
}//abc122_d.復習.解答参考.
```