인접한 모든 자릿수의 차이가 \(1\)인 수를 '계단 수'라고 한다. 예를 들어 \(45656\)은 계단 수이다.

길이가 \(N\)인 계단 수 중에서 \(0\)부터 \(9\)까지의 모든 숫자가 적어도 한 번 이상 등장하는 계단 수의 개수를 구하는 프로그램을 작성하시오.

(단, \(0\)으로 시작하는 수는 계단 수가 아니다.)

입력

첫째 줄에 \(N\)이 주어진다. (\(1 \le N \le 100\))

출력

길이가 \(N\)인 계단 수 중 \(0\)부터 \(9\)까지의 모든 숫자를 포함하는 것의 개수를 \(1,000,000,000\)으로 나눈 나머지를 출력한다.

예제 입력 1

10

예제 출력 1

1

예제 입력 2

15

예제 출력 2

287