#1370 격자 채우기

150  1 s   128 MB  

Description

3행 N열의 격자판이 있다. 이 격자판을 1행 1열짜리 빨간색 타일과 2행 2열짜리 파란색 타일만을 사용하여 빈틈없이 채우려고 한다. 이 때 몇 가지 방법으로 빈틈없이 채울 수 있겠는가?

Input

입력은 한 행에 하나씩의 여러 개의 테스트 케이스로 구성되며, 각 행에는 N (1 <= N <= 100) 이 주어진다. 입력의 끝에는 -1이 N 대신 주어진다.

Output

각 테스트 케이스에 대한 답안을 한 행에 하나씩 출력한다. 단, 답이 매우 클 수 있으므로 1000000009으로 나눈 나머지를 대신 출력한다.

Sample Input

Sample Output

1
3
-1
1
5