조건에 맞는 정수의 개수

양의 정수 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)