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
n=int(input())
mod1,mod2=10**9+7,998244353
mod=mod1
import sys
sys.setrecursionlimit(10**9)
memo=[{}for i in range(n+1)]
def ok(s):
    if "AGC"in s:return False
    for i in range(3):
        if "AGC"in s[:i]+s[i+1]+s[i]+s[i+2:]:
            return False
    return True
def dfs(cnt,las):
    if las in memo[cnt]:return memo[cnt][las]
    if cnt==n:return 1
    ret=0
    for nec in "AGCT":
        if ok(las+nec):
            ret=(ret+dfs(cnt+1,las[1:]+nec))%mod
    memo[cnt][las]=ret
    return ret
print(dfs(0,"TTT"))