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())
dp = [[0]*64 for _ in [0]*n]
mod = 10**9+7

A = 0
C = 1
G = 2
T = 3

AGC = 16*A+4*G+C
ACG = 16*A+4*C+G
GAC = 16*G+4*A+C

for j in range(64):
  if j==AGC or j==ACG or j==GAC:
    dp[2][j] = 0
  else:
    dp[2][j] = 1

for i in range(3, n):
  tot = [sum(dp[i-1][k::16]) for k in range(16)]
  for j in range(64):
    c1 = j//16
    c2 = j//4%4
    c3 = j%4
    d = tot[j//4]

    if j==AGC or j==ACG or j==GAC:
      d = 0
    elif c2==G and c3==C:
      d -= dp[i-1][c1*4+G]
    elif c1==G and c3==C:
      d -= dp[i-1][G*4+c2]
    dp[i][j] = d % mod

print(sum(dp[-1]) % mod)