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
A = [0, 1, 4]
G = [0, 1, 4]
C = [0, 1, 4]
T = [0, 1, 4]
AG = [0, 0, 1]
GA = [0, 0, 1]
AC = [0, 0, 1]
AT = [0, 0, 1]
AGG = [0, 0, 0]
ATG = [0, 0, 0]
AGT = [0, 0, 0]
for i in range(2, 100):
	A.append(A[i]+G[i]+C[i]+T[i])
	G.append(A[i]+G[i]+C[i]+T[i]-AC[i])
	C.append(A[i]+G[i]+C[i]+T[i]-AG[i]-GA[i]-AGG[i]-ATG[i]-AGT[i])
	T.append(A[i]+G[i]+C[i]+T[i])
	AG.append(A[i])
	GA.append(G[i])
	AC.append(A[i]-GA[i])
	AT.append(A[i])
	AGG.append(AG[i])
	ATG.append(AT[i])
	AGT.append(AG[i])
N = int(input())
print((A[N]+G[N]+C[N]+T[N])%(10**9+7))