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

long long dp[10][105];
int main(){
  int n; cin >> n;
  for(int j=0;j<10;j++) dp[j][0] = 0;
  dp[0][0] = 1;
  
  for(int i=1; i <= 100; i++){
  	dp[0][i] = dp[0][i-1]*2+dp[1][i-1]*2 + dp[6][i-1]+ dp[5][i-1]+dp[7][i-1]*2+dp[9][i-1]*2;
    dp[1][i] = dp[1][i-1]+dp[0][i-1]+dp[6][i-1]+dp[5][i-1];
    dp[2][i] = dp[1][i-1]+dp[4][i-1]+dp[5][i-1];
    dp[3][i] = dp[6][i-1]+dp[3][i-1]*4+dp[4][i-1]+dp[5][i-1]+dp[2][i-1]+dp[9][i-1];
    dp[4][i] = dp[2][i-1]+dp[8][i-1];
    dp[5][i] = dp[4][i-1]+dp[7][i-1];
    dp[6][i] = dp[4][i-1];
    dp[7][i] = dp[2][i-1]+dp[8][i-1];
    dp[8][i] = dp[7][i-1]+dp[0][i-1]+dp[2][i-1]+dp[8][i-1]+dp[9][i-1]+dp[6][i-1];
    dp[9][i] = dp[8][i-1];
    for(int j=0;j<10;j++) dp[j][i] %= MOD;
  }
  long long int ans = 0;
  for(int i=0;i<10;i++) ans = (ans + (i!=3 ? dp[i][n]: 0)) % MOD;
  cout << ans << endl;
  return 0;
}
### Prompt

Your challenge is to write 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>
#define MOD 1000000007
using namespace std;

long long dp[10][105];
int main(){
  int n; cin >> n;
  for(int j=0;j<10;j++) dp[j][0] = 0;
  dp[0][0] = 1;
  
  for(int i=1; i <= 100; i++){
  	dp[0][i] = dp[0][i-1]*2+dp[1][i-1]*2 + dp[6][i-1]+ dp[5][i-1]+dp[7][i-1]*2+dp[9][i-1]*2;
    dp[1][i] = dp[1][i-1]+dp[0][i-1]+dp[6][i-1]+dp[5][i-1];
    dp[2][i] = dp[1][i-1]+dp[4][i-1]+dp[5][i-1];
    dp[3][i] = dp[6][i-1]+dp[3][i-1]*4+dp[4][i-1]+dp[5][i-1]+dp[2][i-1]+dp[9][i-1];
    dp[4][i] = dp[2][i-1]+dp[8][i-1];
    dp[5][i] = dp[4][i-1]+dp[7][i-1];
    dp[6][i] = dp[4][i-1];
    dp[7][i] = dp[2][i-1]+dp[8][i-1];
    dp[8][i] = dp[7][i-1]+dp[0][i-1]+dp[2][i-1]+dp[8][i-1]+dp[9][i-1]+dp[6][i-1];
    dp[9][i] = dp[8][i-1];
    for(int j=0;j<10;j++) dp[j][i] %= MOD;
  }
  long long int ans = 0;
  for(int i=0;i<10;i++) ans = (ans + (i!=3 ? dp[i][n]: 0)) % MOD;
  cout << ans << endl;
  return 0;
}
```