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

long long mod = 1000000007;

int main(){
  int n;
  cin >> n;

  vector<long long> aa(n);
  vector<long long> ag(n);
  vector<long long> a_g(n);
  vector<long long> ag_(n);
  vector<long long> ac(n);
  vector<long long> ga(n);
  vector<long long> a(n);
  vector<long long> g(n);
  vector<long long> c(n);
  long long ret = 16;
  a[0] = g[0] = c[0] = 1;
  a[1] = g[1] = c[1] = 4;
  aa[1] = ag[1] = ac[1] = ga[1] = 1;
  for(int i = 2;i < n;i++){
    aa[i] = a[i-1];
    ag[i] = a[i-1];

    a_g[i] = a[i-2];

    ag_[i] = (ag[i-1]*2) % mod;

    ac[i] = (a[i-1]-ga[i-1])%mod;
    if(ac[i] < 0)ac[i] += mod;

    ga[i] = g[i-1];

    a[i] = ret;
    c[i] = (ret - ag[i-1] - ga[i-1] - ag_[i-1] - a_g[i-1])%mod;
    if(c[i] < 0)c[i] += mod;
    
    g[i] = (ret - ac[i-1])%mod;
    if(g[i] < 0)g[i] += mod;
    
    ret = (c[i]+g[i]+2*a[i])%mod;
  }

  cout << ret << endl;
}

### Prompt

In cpp, your task is to solve 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;

long long mod = 1000000007;

int main(){
  int n;
  cin >> n;

  vector<long long> aa(n);
  vector<long long> ag(n);
  vector<long long> a_g(n);
  vector<long long> ag_(n);
  vector<long long> ac(n);
  vector<long long> ga(n);
  vector<long long> a(n);
  vector<long long> g(n);
  vector<long long> c(n);
  long long ret = 16;
  a[0] = g[0] = c[0] = 1;
  a[1] = g[1] = c[1] = 4;
  aa[1] = ag[1] = ac[1] = ga[1] = 1;
  for(int i = 2;i < n;i++){
    aa[i] = a[i-1];
    ag[i] = a[i-1];

    a_g[i] = a[i-2];

    ag_[i] = (ag[i-1]*2) % mod;

    ac[i] = (a[i-1]-ga[i-1])%mod;
    if(ac[i] < 0)ac[i] += mod;

    ga[i] = g[i-1];

    a[i] = ret;
    c[i] = (ret - ag[i-1] - ga[i-1] - ag_[i-1] - a_g[i-1])%mod;
    if(c[i] < 0)c[i] += mod;
    
    g[i] = (ret - ac[i-1])%mod;
    if(g[i] < 0)g[i] += mod;
    
    ret = (c[i]+g[i]+2*a[i])%mod;
  }

  cout << ret << endl;
}

```