문제1370--격자 채우기

1370: 격자 채우기

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 496  통과: 203
[제출] [채점기록] [묻고답하기]

문제 설명

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

입력 설명

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

출력 설명

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

입력 예시 Copy

1
3
-1

출력 예시 Copy

1
5

출처/분류