조건에 맞는 정수의 개수
면접 대비시간 제한1초메모리 제한512 MB
0이 없는 n자리 정수 중 이웃한 두 자리의 차이가 2 이하인 수의 개수를 987654321로 나눈 나머지를 구한다.
문제
양의 정수 n이 주어진다. 아래 조건을 만족하는 양의 정수 A의 개수를 구하자.
- 정수 A는 n개의 자릿수를 갖는 정수이며, 각각의 자릿수는 0이 아니다.
- 정수 A의 이웃한 두 자리의 숫자의 차이는 2 이하이다. 즉, 정수 A의 각 자리의 숫자를 높은 자릿수부터 낮은 자릿수 순서로 A1, A2, ..., An이라고 할 때, |Ai - Ai+1| ≤ 2 (1 ≤ i ≤ n-1) 이다.
입력
첫 번째 줄에 양의 정수 n이 주어진다.
출력
첫 번째 줄에 양의 정수 A의 개수를 987,654,321로 나눈 나머지를 출력한다.
제한
- 1 ≤ n ≤ 100,000
- 1 ≤ Ai ≤ 9 (1 ≤ i ≤ n)