#include <stdio.h>
#define mod 1000000007
#define m 256
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0;
  scanf("%lld", &n);
  ll dp[n][m];
  bool flg[m];
  for(i = 0; i < n; ++i) for(j = 0; j < m; ++j) dp[i][j] = 0;
  if(n == 3) {
    printf("61");
    return 0;
  }
  for(i = 0; i < m; ++i) {
    if((i & 0x3F) == 0x9 || (i & 0x3F) == 0x6 || (i & 0x3F) == 0x21 || (i & 0xCF) == 0x9 || (i & 0xF3) == 0x21 || (i & 0xFC) == 0x24 || (i & 0xFC) == 0x18 || (i & 0xFC) == 0x84) flg[i] = false;
    else flg[i] = true;
  }
  for(i = 0; i < m; ++i) if(flg[i]) dp[3][i] = 1;
  for(i = 4; i < n; ++i) {
    for(j = 0; j < m; ++j) {
      if(flg[j]) for(k = 0; k < m; ++k) if(((k & 0x3F) << 2) == (j & 0xFC)) dp[i][j] += dp[i - 1][k], dp[i][j] %= mod;
    }
  }
  for(i = 0; i < m; ++i) ans += dp[n - 1][i], ans %= mod;
  printf("%lld", ans);
  return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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 <stdio.h>
#define mod 1000000007
#define m 256
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0;
  scanf("%lld", &n);
  ll dp[n][m];
  bool flg[m];
  for(i = 0; i < n; ++i) for(j = 0; j < m; ++j) dp[i][j] = 0;
  if(n == 3) {
    printf("61");
    return 0;
  }
  for(i = 0; i < m; ++i) {
    if((i & 0x3F) == 0x9 || (i & 0x3F) == 0x6 || (i & 0x3F) == 0x21 || (i & 0xCF) == 0x9 || (i & 0xF3) == 0x21 || (i & 0xFC) == 0x24 || (i & 0xFC) == 0x18 || (i & 0xFC) == 0x84) flg[i] = false;
    else flg[i] = true;
  }
  for(i = 0; i < m; ++i) if(flg[i]) dp[3][i] = 1;
  for(i = 4; i < n; ++i) {
    for(j = 0; j < m; ++j) {
      if(flg[j]) for(k = 0; k < m; ++k) if(((k & 0x3F) << 2) == (j & 0xFC)) dp[i][j] += dp[i - 1][k], dp[i][j] %= mod;
    }
  }
  for(i = 0; i < m; ++i) ans += dp[n - 1][i], ans %= mod;
  printf("%lld", ans);
  return 0;
}
```