Problem Statement

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.

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.

Constraints

• $3 \leq N \leq 100$

Sample Input 1

3

Sample Output 1

61

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.

Sample Input 2

4

Sample Output 2

230

Sample Input 3

100

Sample Output 3

388130742

Be sure to print the number of strings modulo 10^9+7.

见题面 Input 部分

见题面 Output 部分