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
N = int(input())
chars = 'AGCT'

dp = {}
for c1 in chars:
    for c2 in chars:
        for c3 in chars:
            dp[c1+c2+c3] = 1
dp['AGC'] = dp['ACG'] = dp['GAC'] = 0

def isValid(s):
    return not (s[1:] == 'AGC' or
                s[1:] == 'ACG' or
                s[1:] == 'GAC' or
                (s[0] == 'A' and s[3] == 'C' and 'G' in s[1:3]) )
	
for i in range(N-3):
    dp_new = {k:0 for k in dp}
    for k in dp:
      	for c in chars:
            if isValid(k+c):
                dp_new[k[1:]+c] += dp[k]
    dp = dp_new

print(sum([v for k,v in dp.items()]) % 1000000007)