#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define mod 1000000007
template<class T> void add(T &a, T b) {a = (a + b) % mod;}

int dp[101][4][4][4];
int main() {
  int N; cin >> N;
  int A = 0, C = 1, G = 2, T = 3;
  dp[0][T][T][T] = 1;
  rep(i, 0, N) rep(j, 0, 4) rep(k, 0, 4) rep(l, 0, 4) rep(m, 0, 4) {
    if(dp[i][j][k][l] == 0) continue;
    if(k == A && l == G && m == C) continue;
    if(k == A && l == C && m == G) continue;
    if(k == G && l == A && m == C) continue;
    if(j == A && k == G && m == C) continue;
    if(j == A && l == G && m == C) continue;
    add(dp[i + 1][k][l][m], dp[i][j][k][l]);
  }
  int ans = 0;
  rep(i, 0, 4) rep(j, 0, 4) rep(k, 0, 4) {
    add(ans, dp[N][i][j][k]);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 rep(i, m, n) for (int i = m; i < n; ++i)
#define mod 1000000007
template<class T> void add(T &a, T b) {a = (a + b) % mod;}

int dp[101][4][4][4];
int main() {
  int N; cin >> N;
  int A = 0, C = 1, G = 2, T = 3;
  dp[0][T][T][T] = 1;
  rep(i, 0, N) rep(j, 0, 4) rep(k, 0, 4) rep(l, 0, 4) rep(m, 0, 4) {
    if(dp[i][j][k][l] == 0) continue;
    if(k == A && l == G && m == C) continue;
    if(k == A && l == C && m == G) continue;
    if(k == G && l == A && m == C) continue;
    if(j == A && k == G && m == C) continue;
    if(j == A && l == G && m == C) continue;
    add(dp[i + 1][k][l][m], dp[i][j][k][l]);
  }
  int ans = 0;
  rep(i, 0, 4) rep(j, 0, 4) rep(k, 0, 4) {
    add(ans, dp[N][i][j][k]);
  }
  cout << ans << endl;
  return 0;
}

```