P1990 Tiling the Wall

You have a wall of length $N$ and width $2$. You are given two types of bricks: one is $2\times 1$, and the other is an L-shaped brick that covers $3$ unit cells. As shown below: ``` 0 0 0 00 ``` Bricks can be rotated, and both types are available in unlimited quantity. Your task is to count the number of ways to tile the $N\times 2$ wall using these two types. For example, a $2\times3$ wall can be tiled in $5$ ways, as follows: ``` 012 002 011 001 011 012 112 022 011 001 ``` Note that the two types can be mixed in a tiling; for example, a $2\times4$ wall can be tiled as follows: ``` 0112 0012 ``` Given $N$, compute the number of tilings for the $2\times N$ wall. Since the result can be large, output only the last $4$ digits. For example, if the number of tilings for $2\times 13$ is $13465$, output $3465$. If the answer has fewer than $4$ digits, output it directly without leading zeros, e.g., when $N=3$, output $5$.

A single integer $N$, the length of the wall.

Output the last $4$ digits of the number of tilings; if it has fewer than $4$ digits, output the entire answer.

Constraints: $1\leq N\leq 1000000$. Translated by ChatGPT 5