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
dame=['AAGC', 'AACG', 'AGAC', 'AGAC', 'AGGC',
      'AGGC', 'AGTC', 'ATGC', 'GAGC', 'GGAC',
      'CAGC', 'CACG', 'CGAC', 'TAGC', 'TACG', 'TGAC']
memo={"TTT":1}

n=int(input())
for i in range(n):
    nmemo={}
    for c in ["A","G","C","T"]:
        for mk,mv in memo.items():
            nk=mk+c
            if nk not in dame:
                nk=nk[1:]
                if nk in nmemo:
                    nmemo[nk]+=mv
                else:
                    nmemo[nk]=mv
    memo=nmemo
print(sum(memo.values())%(10**9+7))