45656이란 수를 보자.

이 수는 인접한 모든 자릿수의 차이가 1이다. 이런 수를 '계단 수'라고 한다.

수의 자릿수 \(N\)이 주어질 때, 길이가 \(N\)인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.

0으로 시작하는 수는 계단 수가 아니다.

입력

첫째 줄에 \(N\)이 주어진다. \(N\)은 1 이상 100 이하의 자연수이다.

출력

첫째 줄에 정답을 \(1,000,000,000\)으로 나눈 나머지를 출력한다.

제한사항

• \(1 \le N \le 100\)

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

예제 설명

• N=1일 때: 1, 2, 3, 4, 5, 6, 7, 8, 9 (총 9개. 0은 맨 앞자리에 올 수 없음)
• N=2일 때: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 (총 17개)