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
# # # coding=utf-8
# # # Author: lee215

get = lambda: int(raw_input().strip())

import collections


def valid(S):
    if "AGC" in S:
        return False
    for i in xrange(len(S)):
        S2 = S[:i] + S[i:i + 2][::-1] + S[i + 2:]
        if "AGC" in S2:
            return False
    return True


N = get()
# N = 100
mod = 10**9 + 7
count = collections.Counter({"": 1})
for _ in xrange(N):
    count2 = collections.Counter({"": 0})
    for pre in count:
        for X in "AGCT":
            cur = pre + X
            if valid(cur):
                count2[cur[-3:]] += count[pre] % mod
    count = count2


print sum(count.values()) % mod
