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;

int a[2][256];
int main() {
	int n, p = 1e9 + 7;
	cin >> n;
	a[1][255] = 1;
	for (int i = 0; i < n; i++) {
		fill(a[i & 1], a[i & 1] + 256, 0);
		for (int j = 0; j < 1024; j++)
			(a[i & 1][j & 0xff] += a[~i & 1][j >> 2]) %= p;
		for (int j = 0; j < 4; j++) {
			a[i & 1][j * 64 + 9] = 0;
			a[i & 1][j * 64 + 33] = 0;
			a[i & 1][j * 64 + 6] = 0;
			a[i & 1][j * 16 + 9] = 0;
			a[i & 1][j * 4 + 33] = 0;
		}
	}
	int r = 0;
	for (int i = 0; i < 256; i++)
		(r += a[~n & 1][i]) %= p;
	cout << r << endl;
	return 0;
}
