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

const int MOD = 1e9 + 7;
vector<vector<int>> memo(200, vector<int>(200));
map<string, int> mp;
int mpidx = 0;

bool ok(string last4) {
  for (int i = 0; i < 4; i++) {
    string t = last4;
    if (i >= 1) {
      swap(t.at(i-1), t.at(i));
    }
    if (t.find("AGC") != string::npos) {
      return false;
    }
  }
  return true;
}

int dfs(int cur, string last3, int N) {
  if (mp.count(last3) == 0) {
    mp[last3] = mpidx;
    mpidx++;
  }
  if (memo.at(cur).at(mp[last3]) != 0) {
    return memo.at(cur).at(mp[last3]);
  }
  if (cur == N) {
    return 1;
  }
  int cnt = 0;
  for (int i = 0; i < 4; i++) {
    string acgt = "ACGT";
    char c = acgt.at(i);
    if (ok(last3 + c)) {
      cnt += dfs(cur + 1, last3.substr(1,2) + c, N);
      cnt %= MOD;
    }
  }
  memo.at(cur).at(mp[last3]) = cnt;
  return cnt;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, "___", N) << endl;;
}
### Prompt

Develop a solution in Cpp 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 <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
vector<vector<int>> memo(200, vector<int>(200));
map<string, int> mp;
int mpidx = 0;

bool ok(string last4) {
  for (int i = 0; i < 4; i++) {
    string t = last4;
    if (i >= 1) {
      swap(t.at(i-1), t.at(i));
    }
    if (t.find("AGC") != string::npos) {
      return false;
    }
  }
  return true;
}

int dfs(int cur, string last3, int N) {
  if (mp.count(last3) == 0) {
    mp[last3] = mpidx;
    mpidx++;
  }
  if (memo.at(cur).at(mp[last3]) != 0) {
    return memo.at(cur).at(mp[last3]);
  }
  if (cur == N) {
    return 1;
  }
  int cnt = 0;
  for (int i = 0; i < 4; i++) {
    string acgt = "ACGT";
    char c = acgt.at(i);
    if (ok(last3 + c)) {
      cnt += dfs(cur + 1, last3.substr(1,2) + c, N);
      cnt %= MOD;
    }
  }
  memo.at(cur).at(mp[last3]) = cnt;
  return cnt;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, "___", N) << endl;;
}
```