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())
M = 10**9 + 7

E = "ACGT"

from collections import defaultdict

ngp = [
    "AGC?", "GAC?", "ACG?",
    "?AGC", "?GAC", "?ACG",
    "A?GC", "AG?C"
]

ng = set(["AGC", "GAC", "ACG"])

for x in ngp:
    for c in E:
        ng.add(x.replace("?", c))

rs = {"": 1}

for i in range(N):
    nrs = defaultdict(int)
    for k, v in rs.items():
        for e in E:
            nk = (k + e)[-4:]
            if not nk in ng:
                nrs[nk[-3:]] += v
    rs = nrs

result = sum(nrs.values()) % M

print(result)