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().strip())
M = pow(10, 9) + 7
a = 1
g = 1
ag = 0
agg = 0
agt = 0
atg = 0
ac = 0
at = 0
aa = 0
ga = 0

al = 4
nal = 0

for i in range(N-1):
    nal = (al * 4) % M
    nal = (nal + M - (ag + ac + ga + agg + agt + atg) ) % M

    agg = ag
    agt = ag
    atg = at
    ag = a
    aa = a
    at = a
    nac = (a + M- ga) % M
    ga = g
    a = al
    g = (al + M - ac) % M
    ac = nac
    al = nal
print(al)
