시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 30 7 6 35.294%

문제

양의 정수의 각 자리의 변화가 증가와 감소를 번갈아가면서 나타날 때, 이 숫자를 "지그재그 수"라고 한다. 예를 들어, 2947은 자리가 2→9→4→7로 증가→감소→증가 순이기 때문에 지그재그 수이다. 또, 71946은 감소→증가→감소→증가이기 때문에 지그재그 수이다. 하지만, 123, 71446, 71442, 88은 지그재그 수가 아니다. 한 자리 정수는 지그재그 수이다.

A이상 B이하의 M의 배수 중 지그재그 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 M이 주어진다. (1 ≤ A ≤ B ≤ 10500, 1 ≤ M ≤ 500)

출력

A이상 B이하의 M의 배수 중 지그재그 수의 개수를 10000으로 나눈 나머지를 출력한다.

예제 입력

100
200
5

예제 출력

13

힌트

105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195