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

int MOD=1000000007;

int main() {
  int N;
  cin >> N;
  vector<vector<long long>> dp(N+1,vector<long long>(4));
  vector<long long> ans(N+1);
  for (int i=0;i<4;i++){
    dp[0][i]=0;
    dp[1][i]=1;
    dp[2][i]=4;
  }
  ans[0]=0;
  ans[1]=4;
  ans[2]=16;
  for (int i=3;i<N+1;i++){
    dp[i][0]=ans[i-1];
    dp[i][1]=ans[i-1];
    dp[i][2]=ans[i-1]-dp[i-2][0]+dp[i-3][2];
    dp[i][3]=ans[i-1]-dp[i-2][0]-dp[i-2][2]-dp[i-3][0]*3;
    ans[i]=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3])%MOD;
  }
  cout << ans[N] << endl;
}
### 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;

int MOD=1000000007;

int main() {
  int N;
  cin >> N;
  vector<vector<long long>> dp(N+1,vector<long long>(4));
  vector<long long> ans(N+1);
  for (int i=0;i<4;i++){
    dp[0][i]=0;
    dp[1][i]=1;
    dp[2][i]=4;
  }
  ans[0]=0;
  ans[1]=4;
  ans[2]=16;
  for (int i=3;i<N+1;i++){
    dp[i][0]=ans[i-1];
    dp[i][1]=ans[i-1];
    dp[i][2]=ans[i-1]-dp[i-2][0]+dp[i-3][2];
    dp[i][3]=ans[i-1]-dp[i-2][0]-dp[i-2][2]-dp[i-3][0]*3;
    ans[i]=(dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3])%MOD;
  }
  cout << ans[N] << endl;
}
```