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
mod = 10**9 + 7
n = int(input())
caps = ['A','G','C','T']
agct = []
for a in caps:
    for b in caps:
        for c in caps:
            if a+b+c not in ['AGC','GAC','ACG']:
                agct.append(a+b+c)

ngs = set(['AGC','GAC','ACG','AGGC','ATGC','AAGC','AGAC','AGTC'])           
dic = {}
for trio in agct:
        dic[trio] =1
for _ in range(n-3):
    dic2 = {x:0 for x in agct}
    for trio in agct:
        for cap in caps:
            quad = trio + cap
            if (not quad in ngs) and (not quad[1:] in ngs):
                dic2[quad[1:]] += dic[trio]
    dic = dic2

print(sum(dic.values())%mod)