어떤 양의 정수에서 각 자리 숫자가 차례로 증가와 감소를 번갈아 때, 그 수를 "지그재그 수"라고 부르기로 하자.

예를 들어, 2947은 자리 숫자가 2 → 9 → 4 → 7 증가 → 감소 → 증가의 순으로 되어 있기 때문에 지그재그 수이다.

또한 71946은 감소 → 증가 → 감소 → 증가 순이므로 지그재그 수이다.

한편, 123이나 71446이나 71442이나 88은 지그재그 수가 아니다.

또한, 1 자리의 양의 정수는 지그재그 수라고 생각한다.

A 이상 B 이하의 M의 배수 중 지그재그 수의 개수를 10000으로 나눈 나머지를 구하는 프로그램을 작성하라.

지그재그 수 (Zig-Zag Numbers) timer 1s memory 64MB

지그재그 수 (Zig-Zag Numbers) 1s 64MB