#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

ll dp[111][5][5][5];

int main(){
  int N; cin>>N;
  dp[0][0][0][0]=1;
  rep(i,N) rep(j,5) rep(k,5) rep(l,5){
    rep(m,4) (dp[i+1][k][l][m+1]+=dp[i][j][k][l])%=MOD;
    if((j==1&&k==3)||(j==1&&l==3)||(k==3&&l==1)||(k==1&&l==3)){
      (dp[i+1][k][l][2]+=MOD-dp[i][j][k][l])%=MOD;
    }
    if(k==1&&l==2){
      (dp[i+1][k][l][3]+=MOD-dp[i][j][k][l])%=MOD;
    }
  }
  ll ans=0;
  rep(i,4) rep(j,4) rep(k,4) (ans+=dp[N][i+1][j+1][k+1])%=MOD;
  cout<<ans<<endl;
  return 0;
}
### Prompt

Generate 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;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

ll dp[111][5][5][5];

int main(){
  int N; cin>>N;
  dp[0][0][0][0]=1;
  rep(i,N) rep(j,5) rep(k,5) rep(l,5){
    rep(m,4) (dp[i+1][k][l][m+1]+=dp[i][j][k][l])%=MOD;
    if((j==1&&k==3)||(j==1&&l==3)||(k==3&&l==1)||(k==1&&l==3)){
      (dp[i+1][k][l][2]+=MOD-dp[i][j][k][l])%=MOD;
    }
    if(k==1&&l==2){
      (dp[i+1][k][l][3]+=MOD-dp[i][j][k][l])%=MOD;
    }
  }
  ll ans=0;
  rep(i,4) rep(j,4) rep(k,4) (ans+=dp[N][i+1][j+1][k+1])%=MOD;
  cout<<ans<<endl;
  return 0;
}
```