P8784 [Lanqiao Cup 2022 NOI Qualifier B] Block Painting

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 an integer $N$, representing the canvas size.

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

**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