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
import itertools

ACGT = ['A', 'C', 'G', 'T', '']
MOD = 10 ** 9 + 7

N = int(input())

dp = [[[[0] * 5
        for _ in range(5)]
       for _ in range(5)]
      for _ in range(N + 1)]
dp[0][4][4][4] = 1

for i, p, q, r, s in itertools.product(range(N), range(5), range(5), range(5), range(4)):
    if ACGT[q] + ACGT[r] + ACGT[s] not in {'AGC', 'GAC', 'ACG'} \
            and ACGT[p] + ACGT[r] + ACGT[s] != 'AGC' \
            and ACGT[p] + ACGT[q] + ACGT[s] != 'AGC':
        dp[i + 1][q][r][s] += dp[i][p][q][r]
        dp[i + 1][q][r][s] %= MOD

print(sum(sum(sum(y) for y in x) for x in dp[N]) % MOD)
