Description

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$.

Input Format

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

Output Format

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

13

3465

Hint

Constraints: $1\leq N\leq 1000000$.

Translated by ChatGPT 5