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 rep(i,n) for(int i=0;i<n;i++)
int main(){
  long long n,a,mod=1e9+7,A[101]={0},C[101]={0},G[101]={0},T[101]={0},AG[101]={0},AC[101]={0},GA[101]={0},AT[101]={0};
  cin>>n;
  A[1]=1,G[1]=1,C[1]=1,T[1]=1;
  for(int i=2;i<=n+1;i++){
    a=(A[i-1]+G[i-1]+C[i-1]+T[i-1])%mod;
    A[i]=a,G[i]=(a-AC[i-1]+mod)%mod,C[i]=(a-AG[i-1]-GA[i-1]-AG[i-2]*2-AT[i-2]+mod*10)%mod,T[i]=a;
    AG[i]=A[i-1],AC[i]=(A[i-1]-GA[i-1]+mod)%mod,GA[i]=G[i-1],AT[i]=A[i-1];
  }
  cout<<a;
}