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
from collections import defaultdict
from itertools import  product
def main():
    N=input()

    dp = [defaultdict(int) for i in range(101)]
    def ok(s):
        if s[:-1] in ("agc", "acg", "gac"):
            return False        
        if s[1:] in ("agc", "acg", "gac"):
            return False
        if s[0:2] == "ag" and s[3] == "c":
            return False
        if s[0] == "a" and s[2:4] == "gc": 
            return False
        return True

    if N==3:
        print(61)
        return

    for s in product("atgc", repeat=4):
        s="".join(s)
        if ok(s):
            dp[4][s]=1
        else:
            dp[4][s]=0
    
    i=5
    while i<=N:
        for k,v in dp[i-1].iteritems():
            for c in "atgc":
                n=k[1:]+c
                if ok(n):
                    dp[i][n] += dp[i-1][k]
        i+=1
    print(sum(dp[N].values()) % (10**9+7))
main()
