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 <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define mod (int)(1e9 + 7)
#define pb push_back
using namespace std;
typedef pair<int,int> pii;

map<pair<int,string>,int> mp;
int N;
string AGCT="AGCT";

int dfs(int n, string s){
  if(s=="AGC") return 0;
  if(mp.find(make_pair(n,s))!=mp.end()) return mp[make_pair(n,s)];
  if(n==N) return 1;

  int ret=0;
  for(int i=0;i<4;i++){
    if(i==2 && s[0]=='A' && s[2]=='G') continue;
    if(i==2 && s[0]=='A' && s[1]=='G') continue;
    if(s.substr(1)+AGCT[i]=="GAC" || s.substr(1)+AGCT[i]=="ACG") continue;
    int tmp=dfs(n+1,s.substr(1)+AGCT[i]);
    ret=(ret+tmp)%mod;
    //cout<<s+AGCT[i]<<endl;
  }
  mp[make_pair(n,s)]=ret;
  return ret;
}

int main(){
  cin>>N;
  cout<<dfs(0,"TTT")<<endl;
  
  return 0;
}

