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
import sys
from collections import deque
import copy
import math
import re

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    dp = [[[[0L for i in range(4)] for j in range(4)] for k in range(4)] for l in range(N + 1)]
    dp[0][3][3][3] = 1
    for i in range(N):
        for c1 in range(4):
            for c2 in range(4):
                for c3 in range(4):
                    for x in range(4):
                        if x == 2 and c2 == 1 and c3 == 0:
                            continue
                        if x == 2 and c1 == 1 and c3 == 0:
                            continue
                        if x == 2 and c2 == 0 and c1 == 1:
                            continue
                        if x == 2 and c2 == 1 and c1 == 0:
                            continue
                        if x == 1 and c2 == 0 and c1 == 2:
                            continue
                        dp[i + 1][c2][c1][x] = (dp[i + 1][c2][c1][x] + dp[i][c3][c2][c1] ) % 1000000007L
    count = 0L
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                    count = (count + dp[N][c1][c2][c3]) % 1000000007L

    print count

##    if N == 3:
##        print 61
##        return
##
##
##    X = N - 3
##    ans = 1L
##    for i in range(N):
##        ans = (ans * 4L) % 1000000007L
##    sub = 26L
##    for i in range(X -1):
##        sub = (sub * 4L) % 1000000007L
##
##    print (ans - sub) % 1000000007L


if __name__ == '__main__':
    main()
