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>
using namespace std;
#define MOD (1000000007)
#define rep(i,k) for(int i=0;i<k;++i)
#define cmp3(i,j,k,p,q,r) (i==p&&j==q&&k==r)
enum AGC{A,G,C};
int main(){
  #define int long
  int n,res=0;
  cin>>n;
  static int dp[101][4][4][4];
  rep(i,4)rep(j,4)rep(k,4) dp[3][i][j][k]=1;
  dp[3][A][G][C] = dp[3][A][C][G] = dp[3][G][A][C] = 0;
  for(int i=4;i<=n;++i){
    rep(c_4,4)rep(c_3,4)rep(c_2,4)rep(c_1,4){
      if(cmp3(c_3,c_2,c_1,A,G,C))continue;
      if(cmp3(c_3,c_2,c_1,A,C,G))continue;
      if(cmp3(c_3,c_2,c_1,G,A,C))continue;
      if(cmp3(c_4,c_2,c_1,A,G,C))continue;
      if(cmp3(c_4,c_3,c_1,A,G,C))continue;
      dp[i][c_3][c_2][c_1]+=dp[i-1][c_4][c_3][c_2]%MOD;
    }
  }
  rep(i,4)rep(j,4)rep(k,4)res+=dp[n][i][j][k]%MOD;
  cout<<res%MOD;
  return 0;
}