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 <cmath>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll dp[110][4][4][4][4];

int main(){
  ll n;
  cin >> n;
  dp[0][3][3][3][3]=1;
  for(ll i=1;i<=n;i++){
    for(ll j=0;j<4;j++){
      for(ll k=0;k<4;k++){
        for(ll l=0;l<4;l++){
          for(ll m=0;m<4;m++){
            if(k==0&&l==1&&m==2||k==0&&l==2&&m==1||k==1&&l==0&&m==2||j==0&&k==1&&m==2||j==0&&l==1&&m==2){
              dp[i][j][k][l][m]=0;
            }
            else{
              for(ll x=0;x<4;x++) dp[i][j][k][l][m]+=dp[i-1][x][j][k][l];
              dp[i][j][k][l][m]%=mod;
            }
          }
        }
      }
    }
  }
  ll ans=0;
  for(ll j=0;j<4;j++){
    for(ll k=0;k<4;k++){
      for(ll l=0;l<4;l++){
        for(ll m=0;m<4;m++){
          ans+=dp[n][j][k][l][m];
          ans%=mod;
        }
      }
    }
  }
  cout << ans << endl;
}          