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
import re

N = int(input())

memo = dict()


def is_agc(text):
    if re.match("(.agc|.acg|.gac|a.gc|ag.c)", text):
        return True
    return False


def dfs(s, m):
    if (s, m) in memo:
        return memo[(s, m)]
    if m == N:
        return 1

    count = 0
    for c in "acgt":
        t = s + c
        if is_agc(t):
            continue
        count += dfs(t[-3:], m+1)

    # print(s, m, count)
    memo[(s, m)] = count % (10**9+7)
    return memo[(s, m)]


print(dfs("ttt", 0))
# print(memo)