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
mod=10**9+7
n=int(input())
A,T,G,C=[0]*(n+1),[0]*(n+1),[0]*(n+1),[0]*(n+1)
A[1],A[2],A[3]=1,4,16
T[1],T[2],T[3]=1,4,16
C[1],C[2],C[3]=1,4,14
G[1],G[2],G[3]=1,4,15
S=[0]*(n+1)
S[1],S[2],S[3]=4,16,61
for i in range(4,n+1):
    A[i],T[i]=S[i-1],S[i-1]
    C[i]=S[i-1]-(A[i-2]+G[i-2]+A[i-3]*3)
    G[i]=S[i-1]-(A[i-2]-G[i-3])
    S[i]=(A[i]+T[i]+C[i]+G[i])%mod
print(S[-1])