타일링

도미노는 $2 \times 1$ 크기의 직사각형 조각이고, 두 칸에는 각각 1부터 6까지의 수가 하나씩 적혀 있다. 원래는 게임에 쓰는 조각이지만 여기서는 다른 용도로 쓴다.

도미노를 겹치지 않게, 빈틈도 남기지 않게 놓으면 너비가 $W$이고 높이가 3인 직사각형을 채울 수 있다. 이렇게 채우는 방법이 몇 가지인지 세는 것이 목표다. 조각에 적힌 수는 아무 역할도 하지 않으므로, 놓인 도미노의 위치와 방향이 하나라도 다르면 서로 다른 방법으로 센다.

아래 그림은 너비가 2이고 높이가 3인 직사각형을 채우는 세 가지 방법이다.

너비가 커지면 채우는 방법도 많아진다. 예를 들어 너비가 12일 때 가능한 답 하나는 다음과 같다.

너비가 $W$이고 높이가 3인 직사각형을 도미노로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 직사각형의 너비 $W$가 주어진다. $1 \le W \le 1000$이다.

첫째 줄에 채우는 방법의 수를 출력한다. 이 값이 매우 커질 수 있으므로 $1000000007$ ($10^9 + 7$)로 나눈 나머지를 출력한다.

$W = 56$일 때 실제 방법의 수는 $8155103542731753$이고, 출력해야 하는 값은 이 수를 $10^9 + 7$로 나눈 나머지다.