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 int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

const int mod = 1000000007;

int dp[625];
int nex[625];

bool check(int p) {
	string s;
	string w = "WATGC";
	rep(i, 5) {
		s.push_back(w[p % 5]);
		p /= 5;
	}
	if(s.find("AGC") != string::npos) {
		return false;
	}
	rep(i, 4) {
		swap(s[i], s[i + 1]);
		if(s.find("AGC") != string::npos) {
			return false;
		}
		swap(s[i], s[i + 1]);
	}
	return true;
}

bool ch[3125];

signed main() {
	int n;
	cin >> n;
	rep(i, 3125) {
		ch[i] = check(i);
	}
	rep(i, 625) {
		dp[i] = 0;
	}
	dp[0] = 1;
	rep(i, n) {
		rep(j, 625) {
			nex[j] = 0;
		}
		rep(j, 625) {
			rep(k, 4) {
				if(ch[(k + 1) * 625 + j]) {
					nex[(k + 1) * 125 + j / 5] += dp[j];
				}
			}
		}
		rep(j, 625) {
			dp[j] = nex[j] % mod;
		}
	}
	int ans = 0;
	rep(i, 625) {
		ans += dp[i];
	}
	cout << ans % mod << endl;
}