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
# -*- coding: utf-8 -*-

N = int(input())

dp = {b: 1 for b in "ACGT"}
for _ in range(N - 1):
    dp_new = {}
    for k in dp:
        for b in "ACGT":
            n = k[-3:] + b
            if n[-3:] in ("AGC", "ACG", "GAC") or n in ("ACGC", "AGGC", "ATGC", "AGCC", "AGGC", "AGTC"):
                continue
            else:
                if n in dp_new:
                    dp_new[n] += dp[k]
                else:
                    dp_new[n] = dp[k]
    dp = dp_new

print(sum(dp.values()) % (10 ** 9 + 7))
