2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 크기의 타일로 빈 공간 없이 채우는 방법의 수를 구하라.

경우의 수가 매우 커질 수 있으므로, 방법의 수를 10007로 나눈 나머지를 출력한다.

점화식: dp[n] = dp[n-1] + dp[n-2], dp[1] = 1, dp[2] = 2.

입출력 예시

입력 1