문제1375--누르기 쉬운 전화번호

1375: 누르기 쉬운 전화번호

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

문제 설명

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

1 2 3
4 5 6
7 8 9
0

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

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

 

입력 설명

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

 

출력 설명

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

 

입력 예시 Copy

2
-1

출력 예시 Copy

26

출처/분류