#include <bits/stdc++.h>
using namespace std;

#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  ll n; cin>>n;
  ll dp[n+1][4][4][4];
  memset(dp,0,sizeof(dp));
  dp[0][3][3][3]=1;

  for (int i=0; i<n; i++) {
    for(int j=0; j<4; j++)for(int k=0; k<4; k++)for(int l=0; l<4; l++)for(int m=0; m<4; m++) {
      if(k==0&&l==1&&m==2) continue;
      if(k==0&&l==2&&m==1) continue;
      if(k==1&&l==0&&m==2) continue;
      if(j==0&&l==1&&m==2) continue;
      if(j==0&&k==1&&m==2) continue;
      dp[i+1][k][l][m] += dp[i][j][k][l];
      dp[i+1][k][l][m] %= mod;
    }
  }

  ll ans=0;
  for(int j=0; j<4; j++)for(int k=0; k<4; k++)for(int l=0; l<4; l++) {
    ans += dp[n][j][k][l];
    ans %= mod;
  }
  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}

### Prompt

Create a solution in Cpp for 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 dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  ll n; cin>>n;
  ll dp[n+1][4][4][4];
  memset(dp,0,sizeof(dp));
  dp[0][3][3][3]=1;

  for (int i=0; i<n; i++) {
    for(int j=0; j<4; j++)for(int k=0; k<4; k++)for(int l=0; l<4; l++)for(int m=0; m<4; m++) {
      if(k==0&&l==1&&m==2) continue;
      if(k==0&&l==2&&m==1) continue;
      if(k==1&&l==0&&m==2) continue;
      if(j==0&&l==1&&m==2) continue;
      if(j==0&&k==1&&m==2) continue;
      dp[i+1][k][l][m] += dp[i][j][k][l];
      dp[i+1][k][l][m] %= mod;
    }
  }

  ll ans=0;
  for(int j=0; j<4; j++)for(int k=0; k<4; k++)for(int l=0; l<4; l++) {
    ans += dp[n][j][k][l];
    ans %= mod;
  }
  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}

```