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
"""
agc
acg
gac
axgc
agxc
"""

n = int(input())
MOD = 10**9 + 7
dpa = [0, 0, 1]
dpc = [0, 0, 1]
dpg = [0, 0, 1]
dpt = [0, 0, 1]

for i in range(2, n+2):
    dpa.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    dpc.append(dpa[i]-dpg[i-1] + dpc[i] + dpg[i]-dpa[i-1]-2*dpa[i-2] + dpt[i]-dpa[i-2])
    dpg.append(dpa[i] + dpc[i]-dpa[i-1]+dpg[i-2] + dpg[i] + dpt[i])
    dpt.append(dpa[i] + dpc[i] + dpg[i] + dpt[i])
    
print((dpa[n+1]+dpg[n+1]+dpc[n+1]+dpt[n+1]) % MOD)