#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define mod 1000000007
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
int dp[110][4][4][4];
signed main(){
	int n,ans=0;
	cin>>n;
	dp[0][0][0][0]=1;
	for(int a=1;a<=n;a++){
		f(b,4){
			f(c,4){
				f(d,4){
					f(e,4){
						if((((a>=3&&c==0)||(a>=4&&b==0))&&d==2&&e==1)||((a>=3&&c==0)&&d==1&&e==2)||(c==2&&(d==0||(a>=4&&b==0))&&e==1))continue;
						dp[a][c][d][e]+=dp[a-1][b][c][d];
						dp[a][c][d][e]%=mod;
					}
				}
			}
		}
	}
	f(i,4){
		f(j,4){
			f(k,4){
				ans+=dp[n][i][j][k];
				ans%=mod;
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}

### 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>
#define int long long
#define P pair<int,int>
#define F first
#define S second
#define f(i,n) for(int i=0;i<(n);i++)
#define INF LLONG_MAX/3
#define eps LDBL_EPSILON
#define mod 1000000007
#define pie 3.141592653589793238462643383279
#define Bpri priority_queue
#define Spri priority_queue<P,vector<P>,greater<P>>
using namespace std;
int dp[110][4][4][4];
signed main(){
	int n,ans=0;
	cin>>n;
	dp[0][0][0][0]=1;
	for(int a=1;a<=n;a++){
		f(b,4){
			f(c,4){
				f(d,4){
					f(e,4){
						if((((a>=3&&c==0)||(a>=4&&b==0))&&d==2&&e==1)||((a>=3&&c==0)&&d==1&&e==2)||(c==2&&(d==0||(a>=4&&b==0))&&e==1))continue;
						dp[a][c][d][e]+=dp[a-1][b][c][d];
						dp[a][c][d][e]%=mod;
					}
				}
			}
		}
	}
	f(i,4){
		f(j,4){
			f(k,4){
				ans+=dp[n][i][j][k];
				ans%=mod;
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}

```