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
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()

D = ['AAGC', 'GAGC', 'CAGC', 'TAGC', 'AGGC', 'ACGC', 'ATGC', 'AGCA', 'AGCG', 'AGCC', 'AGCT', 'AGAC', 'AGGC', 'AGTC']
D += ['ACGA', 'ACGG', 'ACGC', 'ACGT', 'AACG', 'GACG', 'CACG', 'TACG']
D += ['GACA', 'GACG', 'GACC', 'GACT', 'AGAC', 'GGAC', 'CGAC', 'TGAC']
m = {}
for a, b, c in it.product('AGCT', repeat = 3):
    S = a + b + c
    if not S in ['AGC', 'ACG', 'GAC']:
        m[S] = 1
cnt = 0
for _ in range(3, N):
    m2 = {}
    for key in m:
        for c in 'AGCT':
            S = key + c
            if not S in D:
                cnt += 1
                if S[1:] in m2:
                    m2[S[1:]] += m[key]
                    m2[S[1:]] %= MOD
                else:
                    m2[S[1:]] = m[key]
    m = m2
ans = 0
for key in m:
    ans += m[key]
    ans %= MOD
print ans