수문 단계

한 수로에는 수문 N개가 물이 흐르는 방향을 따라 1번부터 N번까지 차례대로 놓여 있다. 각 수문은 0단계부터 9단계까지 열어 둘 수 있다.

수로의 물살이 급하게 바뀌면 수문이 상한다. 그래서 설정에 조건이 하나 붙는다. 번호가 1만큼 차이 나는 두 수문의 단계 차이가 정확히 1이어야 한다. 예를 들어 어떤 수문을 4단계로 열어 두었다면 그 다음 수문은 3단계나 5단계로만 열 수 있다. 4단계나 6단계로 두는 것은 조건에 맞지 않는다.

또한 1번 수문은 물이 가장 먼저 닿는 곳이라 0단계로 둘 수 없다. 2번 수문부터는 0단계로 두어도 된다.

이 조건을 모두 지키는 설정이 몇 가지인지 계산하는 프로그램을 작성하여라. 가짓수가 매우 커질 수 있으므로 가짓수를 1,000,000,000으로 나눈 나머지를 출력한다.

예를 들어 N=2인 상황을 가정하자. 1번 수문의 단계를 먼저 정하고 그에 따라 2번 수문에 올 수 있는 단계를 세어 보면 다음의 표와 같다.

1번 수문은 0단계로 둘 수 없으므로 1단계부터 9단계까지만 생각한다. 1번 수문이 9단계인 경우에는 10단계가 없으므로 2번 수문이 8단계인 경우만 남아 가짓수가 1이다. 표의 가짓수를 모두 더하면 17이므로, 현재 예시에서의 정답은 17이다.

N=1인 경우도 생각해 보자. 이웃한 수문이 없으므로 단계 차이 조건은 따질 것이 없고, 1번 수문을 0단계로 둘 수 없다는 조건만 남는다. 따라서 1단계부터 9단계까지 9가지다.

N=3인 경우에는 설정이 32가지다. N이 2에서 3으로 하나 늘어날 때 가짓수가 17에서 32로 늘어나는데, 두 배가 되지 않는다는 점을 짚어 두자. 0단계 다음에는 1단계만 올 수 있고 9단계 다음에는 8단계만 올 수 있어서, 양쪽 끝의 단계에서는 이어 붙일 수 있는 경우가 하나뿐이기 때문이다.

입출력 예시

예시 1

입력

2

출력

17

예시 2

입력

1

출력

9

예시 3

입력

100

출력

18404112