Problem Description

Yamunaku loves eating snacks. He decided to plan how to eat snacks for the next $N$ days, starting from today as day $1$. He set the following rules:

• He eats snacks three times a day: morning, noon, and evening.
• Each time, he eats one of the following: "cookie", "chocolate", or "cake".
• He does not eat the same snack twice in a row. (This applies to the evening of day $i$ and the morning of day $(i+1)$ as well.)
• He only eats "cookie" or "chocolate" in the morning.

Calculate the number of ways he can follow these rules for $3N$ snacks over $N$ days, modulo $10^9+7$.

Note that he can start with either "cookie" or "chocolate" on the first morning, and he has plenty of all three types of snacks.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

1

Sample Output #1

8

Sample Input #2

2

Sample Output #2

40

Sample Input #3

100000

Sample Output #3

607318103

Notes/Hints

Constraints

• $1\le\ N\le\ 10^{18}$
• $ N $ is an integer

Partial Points

This problem has partial points.

• Correctly solving for inputs where $N\ \leq\ 10^5$ gives $ 300 $ points.

Sample Explanation 1

Representing cookie as "C", cake as "K", and chocolate as "Ch", the combinations for (morning, noon, evening) are: (C, K, C), (C, K, Ch), (C, Ch, C), (C, Ch, K), (Ch, K, C), (Ch, K, Ch), (Ch, Ch, K), (Ch, Ch, Ch). There are 8 ways, noting that the same snack cannot be consecutive and that cake is not eaten in the morning.

见题面 Input 部分

见题面 Output 部分