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
n=int(input())
a=3
b=4
c=4
d=1
e=1
f=1
g=4
h=9
i=12
j=22
for x in range(3,n):
    anew=i
    bnew=c+d+e+h
    cnew=b+i
    dnew=c
    enew=g
    fnew=c
    gnew=b+i
    hnew=d+e+f+h+j
    inew=a+b+f+g+i+j
    jnew=a*2+d+e+f+(g+h+j)*2
    a=anew
    b=bnew
    c=cnew
    d=dnew
    e=enew
    f=fnew
    g=gnew
    h=hnew
    i=inew
    j=jnew
Sum=a+b+c+d+e+f+g+h+i+j
print(Sum%(10**9+7))
    
