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

见题面

见题面