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
MAX_NUM = 10 ** 9 + 7

N = input()
memo = [{} for _ in range(N + 1)]

def ok(last4):
  if 'AGC' in last4 or \
  'GAC' in last4 or \
  'ACG' in last4 or \
  last4[0] == 'A' and last4[2:] == 'GC' or \
  last4[:2] == 'AG' and last4[-1] == 'C':
    return False
  return True

def dfs(cur, last3):
  if cur == N:
    return 1

  if last3 in memo[cur]:
      return memo[cur][last3]

  res = 0
  for c in 'ACGT':
    last4 = last3 + c
    if ok(last4):
      res = (res + dfs(cur + 1, last4[1:])) % MAX_NUM

  memo[cur][last3] = res
  return res

print dfs(0, 'TTT')