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())

t=[1,4,16]
a=[0,1,4]
g=[0,1,4]
c=[0,0,1]
 
for i in range(3, N + 1):
    #print(i)
    t.append(t[i-1]*4 - a[i-2] - c[i-1] - g[i-2] - a[i-3]*3)
    a.append(t[i-1])
    g.append(t[i-1] - c[i-1])
    c.append(t[i-2] - g[i-2])
#print(t,a,g,c)
print(t[N] % (10**9 + 7))