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())
memo = [{} for _ in range(n+1)]

def ok(last4):
  if "AGC" in last4:
    return False
  if "ACG" in last4:
    return False
  if "GAC" in last4:
    return False
  if last4[0] == "A" and last4[2:] == "GC":
  	return False
  if last4[:2] == "AG" and last4[3] == "C":
    return False
  return True

def dfs(cur, last3):
  if last3 in memo[cur]:
    return memo[cur][last3]
  if cur == n:
    return 1
  ret = 0
  for c in "ACGT":
    if (ok(last3 + c)):
      ret += dfs(cur+1, last3[1:] + c)
  memo[cur][last3] = ret
  return ret

print(dfs(0, "TTT") % 1000000007)