Problem Description

Xiaoming has recently become interested in block paintings. There are two types of blocks: the $I$ block (area of $2$ unit squares) and the $L$ block (area of $3$ unit squares):

At the same time, Xiaoming has a canvas of size $2 \times N$. The canvas consists of $2 \times N$ regions of size $1 \times 1$. He needs to completely fill the canvas using the two types of blocks above, and he wants to know how many different ways there are in total. The blocks can be rotated freely, and the orientation of the canvas is fixed.

Input Format

Input an integer $N$, representing the canvas size.

Output Format

Output an integer representing the answer. Since the answer may be very large, output the value modulo $1000000007$ (i.e. $10^9+7$).

3

5

Hint

Sample Explanation

The five cases are shown in the figure below. The colors are only used to distinguish different blocks.

Constraints

For all testdata, $1 \leq N \leq 10^7$.

Lanqiao Cup 2022 Provincial Contest B Group, Problem G.

Translated by ChatGPT 5