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;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;


const ll mod=1000000007;
const ll inf=1e+16; 

#define rep(i,m,n) for(ll i=m;i<n;i++)

ll dp[105][4][4][4]; //A,G,C,T

int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);

 ll n;
  cin >> n;
  dp[0][3][3][3]=1; 
  
  rep(i,0,n){
   rep(j,0,4){
    rep(k,0,4){
     rep(l,0,4){
      rep(m,0,4){
        if(j==0&&k==1&&m==2) continue; //AGXC
        if(k==0&&l==1&&m==2) continue; //XAGC
        if(j==0&&l==1&&m==2) continue; //AXGC
        if(k==1&&l==0&&m==2) continue; //XGAC
        if(k==0&&l==2&&m==1) continue; //XACG
        (dp[i+1][k][l][m]+=dp[i][j][k][l])%=mod;
      }
      } 
    }
   }
  }
  
  ll res=0;
  rep(j,0,4){
   rep(k,0,4){
    rep(l,0,4){
     (res+=dp[n][j][k][l])%=mod; 
    }
   }
  }
  cout <<res << endl;
}
