#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MOD=1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main() {
  IOS;
  ll n;
  cin>>n;
  ll dp[n+1][5][5][5];
  rep(i,n+1) rep(j,5) rep(k,5) rep(l,5) dp[i][j][k][l]=0;
  dp[0][0][0][0]=1;
  rep(_,n) rep(i,5) rep(j,5) rep(k,5) Rep(l,5){
    if(j==1 && k==3 && l==2) continue;
    if(j==1 && k==2 && l==3) continue;
    if(j==3 && k==1 && l==2) continue;
    if(i==1 && j==3 && l==2) continue;
    if(i==1 && k==3 && l==2) continue;
    //貰う方に注目、j,k,lで場合分けする
    dp[_+1][j][k][l]+=dp[_][i][j][k];
    dp[_+1][j][k][l]%=MOD;
  }
  ll ans=0;
  rep(i,5) rep(j,5) rep(k,5) ans+=dp[n][i][j][k],ans%=MOD;
  cout<<ans<<endl;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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 int ll;
const int MOD=1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main() {
  IOS;
  ll n;
  cin>>n;
  ll dp[n+1][5][5][5];
  rep(i,n+1) rep(j,5) rep(k,5) rep(l,5) dp[i][j][k][l]=0;
  dp[0][0][0][0]=1;
  rep(_,n) rep(i,5) rep(j,5) rep(k,5) Rep(l,5){
    if(j==1 && k==3 && l==2) continue;
    if(j==1 && k==2 && l==3) continue;
    if(j==3 && k==1 && l==2) continue;
    if(i==1 && j==3 && l==2) continue;
    if(i==1 && k==3 && l==2) continue;
    //貰う方に注目、j,k,lで場合分けする
    dp[_+1][j][k][l]+=dp[_][i][j][k];
    dp[_+1][j][k][l]%=MOD;
  }
  ll ans=0;
  rep(i,5) rep(j,5) rep(k,5) ans+=dp[n][i][j][k],ans%=MOD;
  cout<<ans<<endl;
}
```