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
from itertools import product

N = int(input())
T = [''.join(t) for t in product(('A','C','G','T'),repeat = 3)]

def acg(s):
    return any(['ACG' in s[:i] + s[i+1:i+2] + s[i] + s[i+2:] for i in range(len(s))])

@lru_cache(maxsize=None)
def f(N,s):
    if N == 3 and acg(s):
        return 0
    elif N == 3 and not acg(s):
        return 1
    else: 
        return sum(f(N-1, c + s[:2]) for c in ('A','C','G','T') if not acg(c + s))

ans = sum(f(N,s) for s in T)
print(ans % 1000000007)