2 by n Tiling

Write a program that counts the ways to fill a 2 by $n$ rectangle completely with 1 by 2 tiles and 2 by 1 tiles. Tiles may not overlap and may not stick out of the rectangle.

The picture below shows one way to fill a 2 by 5 rectangle.

The first line contains $n$. ($1 \le n \le 1{,}000$)

Print the number of ways to fill the 2 by $n$ rectangle, modulo $10{,}007$, on the first line.