#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  int n;
  cin >> n;
  LL p = 1000000007ll;
  LL dp[101][4][4][4];
  REP(i,101) REP(j,4) REP(k,4) REP(l,4) dp[i][j][k][l] = 0ll;
  dp[0][3][3][3] = 1ll;
  REP(i,100) REP(j,4) REP(k,4) REP(l,4) REP(m,4) {
    if(k==0 && l==1 && m== 2) continue;
    if(k==1 && l==0 && m== 2) continue;
    if(k==0 && l==2 && m== 1) 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] %= p;
  }
  LL answer = 0ll;
  REP(j,4) REP(k,4) REP(l,4) {
    answer += dp[n][j][k][l];
    answer %= p;
  }
  cout << answer << 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>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(void)
{
  int n;
  cin >> n;
  LL p = 1000000007ll;
  LL dp[101][4][4][4];
  REP(i,101) REP(j,4) REP(k,4) REP(l,4) dp[i][j][k][l] = 0ll;
  dp[0][3][3][3] = 1ll;
  REP(i,100) REP(j,4) REP(k,4) REP(l,4) REP(m,4) {
    if(k==0 && l==1 && m== 2) continue;
    if(k==1 && l==0 && m== 2) continue;
    if(k==0 && l==2 && m== 1) 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] %= p;
  }
  LL answer = 0ll;
  REP(j,4) REP(k,4) REP(l,4) {
    answer += dp[n][j][k][l];
    answer %= p;
  }
  cout << answer << endl;
  return 0;
}

```