#include<bits/stdc++.h>
using namespace std;
#define int long
const int mod = 1e9+7;
#define rep(a,b) for(int a=0;a<b;++a)
signed main(){
  int n,r=0;
  cin>>n;
  int dp[110][5][5][5][5]={0};
  const int A=0,C=1,G=2,T=3;
  rep(a,4)dp[0][T][T][T][a]=1;
  rep(b,4)rep(a,4)dp[1][T][T][a][b]=1;
  rep(c,4)rep(b,4)rep(a,4)dp[2][T][a][b][c]=1;
  dp[2][T][A][G][C] = dp[2][T][A][C][G] = dp[2][T][G][A][C] = 0;
  for(int i=3;i<n;++i){
    rep(a,4)rep(b,4)rep(c,4)rep(d,4)rep(e,4) dp[i][a][b][c][d] = (dp[i][a][b][c][d] + dp[i-1][e][a][b][c]) % mod;
    rep(a,4)dp[i][A][a][G][C] = dp[i][a][G][A][C] = dp[i][a][A][C][G] = dp[i][a][A][G][C] = dp[i][A][G][a][C] = 0;
  }
  rep(a,4)rep(b,4)rep(c,4)rep(d,4)r=(r+dp[n-1][a][b][c][d])%mod;
  cout<<r;
}
### Prompt

Please create a solution in CPP 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;
#define int long
const int mod = 1e9+7;
#define rep(a,b) for(int a=0;a<b;++a)
signed main(){
  int n,r=0;
  cin>>n;
  int dp[110][5][5][5][5]={0};
  const int A=0,C=1,G=2,T=3;
  rep(a,4)dp[0][T][T][T][a]=1;
  rep(b,4)rep(a,4)dp[1][T][T][a][b]=1;
  rep(c,4)rep(b,4)rep(a,4)dp[2][T][a][b][c]=1;
  dp[2][T][A][G][C] = dp[2][T][A][C][G] = dp[2][T][G][A][C] = 0;
  for(int i=3;i<n;++i){
    rep(a,4)rep(b,4)rep(c,4)rep(d,4)rep(e,4) dp[i][a][b][c][d] = (dp[i][a][b][c][d] + dp[i-1][e][a][b][c]) % mod;
    rep(a,4)dp[i][A][a][G][C] = dp[i][a][G][A][C] = dp[i][a][A][C][G] = dp[i][a][A][G][C] = dp[i][A][G][a][C] = 0;
  }
  rep(a,4)rep(b,4)rep(c,4)rep(d,4)r=(r+dp[n-1][a][b][c][d])%mod;
  cout<<r;
}
```