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<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
#define ll long long
using namespace std;

const int MOD = 1000000007;
int dp[101][4][4][4];

int main() {
  int n; cin>>n;
  dp[0][3][3][3]=1;
  rep(i, n) {
    rep(c1, 4) {
      rep(c2, 4) {
        rep(c3, 4) {
          rep(new_c, 4) {;
            if (new_c==1&&c1==2&&c2==0) continue;
            if (new_c==2&&c1==1&&c2==0) continue;
            if (new_c==2&&c1==1&&c3==0) continue;
            if (new_c==2&&c1==0&&c2==1) continue;
            if (new_c==2&&c2==1&&c3==0) continue;
            dp[i+1][new_c][c1][c2]+=dp[i][c1][c2][c3];
            dp[i+1][new_c][c1][c2]%=MOD;
          }
        }
      }
    }
  }
  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;
}
