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())

t = [0] * (n + 1)
a = [0] * (n + 1)
g = [0] * (n + 1)
ac = [0] * (n + 1)

t[0] = 1
t[1] = 4
t[2] = 16
a[1] = 1
a[2] = 4
g[1] = 1
g[2] = 4
ac[2] = 1

for i in range(3, n + 1):
    t[i] = t[i - 1] * 4 - a[i - 2] - ac[i - 1] - g[i - 2] - a[i - 3] * 3
    a[i] = t[i - 1]
    g[i] = t[i - 1] - ac[i - 1]
    ac[i] = t[i - 2] - g[i - 2]

print(t[n] % (10**9 + 7))