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>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
typedef pair<int, string> P;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
string S;
int N;
map<P, ll> mp;
bool judge(string s){
    string str = s;
    rep(i,0,4){
        if(i < 3)swap(str[i], str[i+1]);
        rep(j,0,2)if(str.substr(j,3) == "AGC"){
            //cout << S << endl;
            return 0;
        }
        swap(str[i], str[i+1]);
    }
    return 1;
}
int dfs(int i, string str){
    if(mp[P(i, str) ] != 0){
        return mp[P(i, str)];
    }
    if(i == N)return 1;
    
    string s = "AGCT";
    ll ret = 0;
    for(auto c:s){
        string ss = str;
        ss += c;
        if(judge(ss)){
            ret = (ret + dfs(i + 1, str.substr(1) += c )) % MOD;
        }
    }
    mp[P(i, str)] = ret;
    
    return ret;
}
int main(){
    cin >> N;
    cout << dfs(0, "TTT") << endl;
}