지그재그 숫자

양의 정수의 각 자리의 변화가 증가와 감소를 번갈아가면서 나타날 때, 이 숫자를 "지그재그 수"라고 한다. 예를 들어, 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으로 나눈 나머지를 출력한다.