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 <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

ll dp[128][4][4][4];
const ll MOD = 1000000000 + 7;
int main() {
  int N; cin>>N;
  REP(i,4) REP(j,4) REP(k,4) dp[3][i][j][k] = 1;
  dp[3][0][2][1] = 0;
  dp[3][0][1][2] = 0;
  dp[3][2][0][1] = 0;
  for(int n = 4; n <= N; n++) {
    REP(i,4) REP(j,4) REP(k,4) REP(m,4)
    {
      if(i == 0 && k == 2 && m == 1) {
        dp[n][j][k][m] = 0;
      } else if(i == 0 && j == 2 && m == 1) {
        dp[n][j][k][m] = 0;
      } else {
        dp[n][j][k][m] += dp[n-1][i][j][k];
        dp[n][j][k][m] %= MOD;
      }
    }
    dp[n][0][2][1] = 0;
    dp[n][0][1][2] = 0;
    dp[n][2][0][1] = 0;
  }
  ll ans = 0;
  REP(i,4) REP(j,4) REP(k,4) ans += dp[N][i][j][k];
  ans %= MOD;
  cout << ans << endl;
  return 0;
}
