2×n 타일링 2

$2 \times n$ 직사각형을 $1 \times 2$, $2 \times 1$, $2 \times 2$ 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 타일은 서로 겹치지 않아야 하고, 직사각형 밖으로 나가지 않아야 하며, 빈칸이 남아서도 안 된다.

타일을 놓은 자리가 하나라도 다르면 서로 다른 방법으로 센다.

첫째 줄에 $n$이 주어진다. ($1 \le n \le 1000$)

첫째 줄에 $2 \times n$ 직사각형을 채우는 방법의 수를 $10007$로 나눈 나머지를 출력한다.