오르막 수

면접 대비

시간 제한1초메모리 제한256 MB

요약

0으로 시작해도 되는 길이 N인 숫자 중 각 자릿수가 왼쪽에서 오른쪽으로 감소하지 않는 개수를 10007로 나눈 나머지로 구합니다.

문제

오르막 수는 각 자리 숫자가 왼쪽에서 오른쪽으로 갈수록 작아지지 않는 수다. 인접한 두 자리가 같아도 오르막 수로 친다.

예를 들어 2234, 3678, 11119는 오르막 수이지만 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 $N$ 이 주어졌을 때 길이가 $N$ 인 오르막 수가 몇 개인지 세는 프로그램을 작성하시오. 맨 앞자리가 0이어도 된다.

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

첫째 줄에 길이가 $N$ 인 오르막 수의 개수를 $10007$ 로 나눈 나머지를 출력한다.