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
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

long long table[200][64];

int main() {
  int N;
  long long t = 0;

  cin >> N;

  for (int j = 3; j <= N; j++) {
    for (int k = 0; k < 256; k++) {
      int l1 = k % 4, l2 = k % 16, l3 = k % 64, t1 = k / 64, t2 = k / 16, t3 = k / 4, m2 = l3 / 4;

      if (j == 3) table[j][l3] = !(l3 == 6 || l3 == 9 || l3 == 33);
      else {
        if (t1 == 0 && l2 == 9 ||
            t2 == 2 && l1 == 1 ||
            l3 == 6 || l3 == 9 || l3 == 33) continue;
        table[j][l3] = (table[j][l3] + table[j - 1][t3]) % 1000000007;
      }
    }
  }

  for (int i = 0; i < 64; i++) t = (t + table[N][i]) % 1000000007;

  cout << t << endl;
}

