Filling a 4 × n Rectangle with Dominoes

You have $2n$ dominoes of width 1 and length 2, where $n$ is an integer smaller than $1000$. These dominoes can be arranged without overlap so that they exactly cover a $4 \times n$ rectangle. Figure 1 covers a $4 \times 6$ rectangle with 12 dominoes.

Figure 1: an example with $n = 6$.

For $n > 1$ there is more than one arrangement. Figure 2 shows all 5 ways of covering a $4 \times 2$ rectangle.

Figure 2: the 5 ways of covering a $4 \times 2$ rectangle.

Let $R_n$ be the number of different ways to cover a $4 \times n$ rectangle with $2n$ dominoes. Figure 2 gives $R_2 = 5$. Even for small $n$ the value of $R_n$ becomes very large, so what you report is its last three digits, that is $R_n$ modulo $1000$.

One integer $n$ on a single line. Remember that $n < 1000$.

Print $R_n$ modulo $1000$ on one line, without leading zeros. For example $R_{17} = 26915305$, so $n = 17$ gives $305$, and $R_2 = 5$, so $n = 2$ gives $5$ and not $005$. When the remainder is zero, print a single $0$.