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())
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  # 先頭の方はチェック済み
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])[-4:]
  return v
 
memo = {}  # 今の長さと最新4つだけメモする
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]
 
print(f(0, '') % int(1e9+7))