#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const ll inf = 1e16;
const ll md = 1000000007;
ll dp[105][4][4][4];

int main() {
  int n;
  cin>>n;
  dp[0][3][3][3]=1LL;
  rep(i,n) rep(c3,4) rep(c2,4) rep(c1,4){
    ll pre=dp[i][c3][c2][c1];
    rep(c0,4){
      if(c0==2){
        if(c2==0 && c1==1) continue;
        if(c3==0 && c1==1) continue;
        if(c2==1 && c1==0) continue;
        if(c3==0 && c2==1) continue;
      }
      if(c2==0 && c1==2 && c0==1) continue;
      dp[i+1][c2][c1][c0]+=pre;
      dp[i+1][c2][c1][c0]%=md;
    }
  }
  ll ans=0;
  rep(c3,4) rep(c2,4) rep(c1,4){
    ans+=dp[n][c3][c2][c1];
    ans%=md;
  }
  cout<<ans<<endl;
  return 0;
}

### Prompt

Please formulate 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;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const ll inf = 1e16;
const ll md = 1000000007;
ll dp[105][4][4][4];

int main() {
  int n;
  cin>>n;
  dp[0][3][3][3]=1LL;
  rep(i,n) rep(c3,4) rep(c2,4) rep(c1,4){
    ll pre=dp[i][c3][c2][c1];
    rep(c0,4){
      if(c0==2){
        if(c2==0 && c1==1) continue;
        if(c3==0 && c1==1) continue;
        if(c2==1 && c1==0) continue;
        if(c3==0 && c2==1) continue;
      }
      if(c2==0 && c1==2 && c0==1) continue;
      dp[i+1][c2][c1][c0]+=pre;
      dp[i+1][c2][c1][c0]%=md;
    }
  }
  ll ans=0;
  rep(c3,4) rep(c2,4) rep(c1,4){
    ans+=dp[n][c3][c2][c1];
    ans%=md;
  }
  cout<<ans<<endl;
  return 0;
}

```