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
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

N = int(input())
MOD = 10**9 + 7
S = ['A', 'G', 'C', 'T']
M = set(['AGC', 'GAC', 'ACG'])

for s in S:
    M.add(s + 'AGC')
    M.add(s + 'GAC')
    M.add(s + 'ACG')
    M.add('A' + s + 'GC')
    M.add('AG' + s + 'C')

@lru_cache(maxsize=None)
def search(prev, length):
    if length >= N:
        return 1

    ret = 0

    for s in S:
        T = prev + s
        if not T in M:
            T = T[:: -1][: 3][:: -1]
            ret += search(T, length + 1)
    return ret

ans = search('', 0) % MOD
print(ans)
