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())
mod=10**9+7
a,f=1,1
l=2
b,c,d,e,g,h,i,j,k=0,0,0,0,0,0,0,0,0

for p in range(N-1):
    A=(d+e+i+l)%mod
    B=(a+g)%mod
    C=(b+j)%mod
    D=(b+j)%mod
    E=(a+h)%mod
    F=(c+d+f+k+l)%mod
    G=(b+c+f+j+k)%mod
    H=(a+g+h)%mod
    I=(a+g+h)%mod
    J=(h)%mod
    K=(i)%mod
    L=(c+d+2*e+2*f+2*i+k+2*l)%mod
    a,b,c,d,e,f,g,h,i,j,k,l=A,B,C,D,E,F,G,H,I,J,K,L
print((a+b+c+d+e+f+g+h+i+j+k+l)%mod)