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
import itertools
from collections import defaultdict

N=input()

if N==3:
	print 61
	quit()

dp=defaultdict(lambda: 0)	#dp[ (n,i,j,k,l) ]
a=0;g=1;c=2;t=3

n=4
for i,j,k,l in itertools.product( range(4), repeat=4 ):
	if l==c and j==g and i==a: continue
	elif l==c and k==g and i==a: continue
	elif l==c and k==g and j==a: continue
	elif k==c and j==g and i==a: continue
	elif l==c and k==a and j==g: continue
	elif k==c and j==a and i==g: continue
	elif l==g and k==c and j==a: continue
	elif k==g and j==c and i==a: continue
	dp[ (n,i,j,k,l) ]=1



for n in range(5,N+1):
	for i,j,k,l in itertools.product( range(4), repeat=4 ):
		if l==c and j==g and i==a: continue
		elif l==c and k==g and i==a: continue
		elif l==c and k==g and j==a: continue
		elif k==c and j==g and i==a: continue
		elif l==c and k==a and j==g: continue
		elif k==c and j==a and i==g: continue
		elif l==g and k==c and j==a: continue
		elif k==g and j==c and i==a: continue
	
		for m in range(4):
			dp[ (n,i,j,k,l) ]+=dp[ (n-1,j,k,l,m) ]


ans=0
for x,val in dp.items():
	n=x[0]
	if n==N:
		ans+=val

print ans%(10**9+7)
