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 collections import defaultdict as dd
n = int(input())
mod,x,y,ans = 10**9+7,{"TTT":1},dd(int),0
def f(s):
    if s[1:]=="AG" or s[1:]=="GA" or s[:2]=="AG" or (s[0]=="A" and s[2]=="G"): return True
    else: return False
def make(s):
    global y
    for i in "ATGC":
        if (s[1:]=="AC" and i=="G") or (f(s) and i=="C"): pass
        else: y[s[1:]+i] = (y[s[1:]+i]+x[s])%mod
for i in range(n):
    for j in x.keys(): make(j)
    x,y = y,dd(int)
for i in x.values(): ans = (ans+i)%mod
print(ans)