레이팅 미적용설명
正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき,その数は「ジグザグ数」であると呼ぶことにしよう.たとえば,2947 は桁の数字が 2 → 9 → 4 → 7 と,増加 → 減少 → 増加 の順になっているのでジグザグ数である.また,71946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である.一方,123 や 71446 や 71442 や 88 はジグザグ数ではない.なお,1 桁の正の整数はジグザグ数であると考えることとする.
A 以上 B 以下の M の倍数のうち,ジグザグ数の個数を 10000 で割った余りを求めるプログラムを作成せよ.
제약
입력 형식
入力は 3 行からなり,1 行に 1 つずつ正の整数が書かれている.
1 行目の整数は A を,2 行目の整数は B を,3 行目の整数は M を表す.これらは 1 ≦ A ≦ B ≦ 10 500 ,1 ≦ M ≦ 500 を満たす.
※ A や B の値は,通常の整数を表すデータ型には収まらない可能性があることに注意せよ.
출력 형식
A 以上 B 以下の M の倍数のうち,ジグザグ数の個数を 10000 で割った余りを 1 行で出力せよ.
예제 1
입력
100
200
5출력
13문제 정보