JOI 2011/2012 예선 6- 지그재그 수 (Zig-Zag Numbers) > 문제은행 : 정보올림피아드&알고리즘


2934 : 지그재그 수 (Zig-Zag Numbers)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
4 회   
시도횟수
68 회   

문제

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

 

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

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

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

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

 

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

 


입력형식

입력은 3 행으로 이루어지며, 한 줄에 하나씩 양의 정수가 적혀있다.

첫 행에 정수 A를 두 번째 행의 정수는 B를 세 번째 줄의 정수는 M이 입력 된다. (1 ≤ A ≤ B ≤ 10500, 1 ≤ M ≤ 500)

※ A와 B의 값은 long long 정수의 범위를 초과할 수 있다는 점에 유의하라.


출력형식

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

입력 예

100
200
5

출력 예

13

입력 예

6
1234567
3

출력 예

246


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP