도미노로 4 × n 직사각형 채우기

가로 1, 세로 2인 도미노 $2n$개가 있다. 여기서 $n$은 $1000$보다 작은 정수다. 이 도미노를 겹치지 않게 놓아 $4 \times n$ 직사각형을 빈틈없이 채울 수 있다. 그림 1은 도미노 12개로 $4 \times 6$ 직사각형을 채운 모습이다.

그림 1: $n = 6$인 예.

$n > 1$이면 채우는 방법이 여러 가지다. 그림 2는 $4 \times 2$ 직사각형을 채우는 5가지 방법을 모두 보여 준다.

그림 2: $4 \times 2$ 직사각형을 채우는 5가지 방법.

도미노 $2n$개로 $4 \times n$ 직사각형을 채우는 서로 다른 방법의 수를 $R_n$이라 하자. 그림 2에서 보듯 $R_2 = 5$다. $n$이 작아도 $R_n$은 매우 커지므로, 구하는 값은 $R_n$의 마지막 세 자리, 즉 $R_n$을 $1000$으로 나눈 나머지다.

정수 $n$이 한 줄에 주어진다. $n < 1000$임을 기억하라.

$R_n$을 $1000$으로 나눈 나머지를 앞에 $0$을 붙이지 않고 한 줄에 출력한다. 예를 들어 $R_{17} = 26915305$이므로 $n = 17$이면 $305$를 출력하고, $R_2 = 5$이므로 $n = 2$이면 $005$가 아니라 $5$를 출력한다. 나머지가 $0$이면 $0$ 하나만 출력한다.