시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB2001286985.185%

문제

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

  • 정수 An개의 자릿수를 갖는 정수이며, 각각의 자릿수는 0이 아니다.
  • 정수 A의 이웃한 두 자리의 숫자의 차이는 2 이하이다. 즉, 정수 A의 각 자리의 숫자를 높은 자릿수부터 낮은 자릿수 순서로 A1, A2, ..., An이라고 할 때, |Ai - Ai+1| ≤ 2 (1 ≤ in-1) 이다.

입력

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

출력

첫 번째 줄에 양의 정수 A의 개수를 987,654,321로 나눈 나머지를 출력한다.

제한

  • 1 ≤ n ≤ 100,000
  • 1 ≤ Ai ≤ 9 (1 ≤ in)

서브태스크

번호배점제한
110

1 ≤ n ≤ 7

220

1 ≤ n ≤ 10

370

1 ≤ n ≤ 100,000

예제 입력 1

1

예제 출력 1

9

1개의 자릿수를 갖는 양의 정수 1, 2, 3, ..., 9가 A에 해당된다. 따라서 정답은 9이다.

예제 입력 2

2

예제 출력 2

39

2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다.

예제 입력 3

100

예제 출력 3

736753518

출처

채점 및 기타 정보

  • 예제는 채점하지 않는다.