#1375 누르기 쉬운 전화번호

106  1 s   128 MB  

Description

보통의 전화기의 다이얼은 아래와 같이 생겼다.

1 2 3
4 5 6
7 8 9
0

이와 같은 다이얼에서 누르기 쉬운 전화번호란, 누르는 숫자들이 순서대로 인접한 전화번호를 뜻한다. (111은 누르기 쉬운 전화번호가 아니다)

길이가 N인 누르기 쉬운 전화번호가 모두 몇 개인지 세는 프로그램을 작성하여라.

 

Input

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

 

Output

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

 

Sample Input

Sample Output

2
-1
26