| 지그재그 수 |
|---|
양의 정수(앞에 0을 붙이지 않고)을 10진수로 표시한 후 숫자를 하나하나 차례로 살펴보았을 때 그 숫자가 증가와 감소를 번갈아 나타나면 그 숫자는 "지그재그 수"라고 부르기로 하자. 예를 들어, 2947은 각 자리수가 2 → 9 → 4 → 7, 즉, 증가 → 감소 → 증가 순서로 되어 있기 때문에 지그재그 수다. 42과 88은 지그재그 수가 아니다. 또한 한 자리 양의 정수는 지그재그 수라고 가정한다. A 이상 B 이하의 M의 배수 중 지그재그 수의 개수를 10000으로 나눈 나머지를 구하는 프로그램을 작성하시오. |
| 입력 | |
|---|---|
1번째 줄에서는 정수 A가, 2번째 줄에는 정수 B가, 3번째 줄에는 정수 M이 주어진다. (1 <= A <= B <= 10500, 1 <= M <= 50) ※ A와 B의 값은 일반적으로 정수를 나타내는 데이터 형식에 맞지 않을 수 있음에 유의하라. | |
| 출력 | |
|---|---|
1번째 줄에 A 이상 B 다음 M의 배수 중 지그재그의 개수를 10000으로 나눈 나머지를 출력한다. ※ 예시1의 경우, 100 이상 200 이하의 5 배수인 지그재그 수는 105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195의 13 개이다 . ※ 예시2의 경우, 6 이상 1234567 이하의 3의 배수인 지그재그 수는 50246 개 있으므로, 그것을 10000으로 나눈 나머지 246을 출력한다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 100 200 5 | |
| 출력 | 13 | ||
| 2 | 입력 | 6 1234567 3 | |
| 출력 | 246 | ||