조건에 맞는 정수의 개수

면접 대비

시간 제한1초메모리 제한512 MB

요약

각 자리가 0이 아니고 인접한 두 자리의 차이가 2 이하인 n자리 양의 정수의 개수를 987,654,321로 나눈 나머지를 구합니다.

문제

양의 정수 $n$ 이 주어진다. 아래 조건을 만족하는 양의 정수 $A$ 의 개수를 구한다.

$A$ 는 $n$ 자리 정수이며, 각 자릿수는 0이 아니다.
$A$ 의 이웃한 두 자릿수의 차이는 2 이하이다. $A$ 의 각 자릿수를 높은 자릿수부터 낮은 자릿수 순서로 $A_1, A_2, \ldots, A_n$ 이라 하면, $|A_i - A_{i+1}| \le 2$ ( $1 \le i \le n-1$ )이다.

첫 번째 줄에 양의 정수 $n$ 이 주어진다.

조건을 만족하는 양의 정수 $A$ 의 개수를 987,654,321로 나눈 나머지를 첫 번째 줄에 출력한다.