10126 쉬운 계단 수 Silver I

문제

인접한 자리의 차이가 모두 1인 수를 계단 수라 한다. N자리 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 구하시오. 0으로 시작하는 수는 제외한다.

입력

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

출력

답을 출력한다.

1

9

2

17