F - ジグザグ数 (Zig-Zag Numbers) Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点: 100

問題

正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき,その数は「ジグザ グ数」であると呼ぶことにしよう.たとえば, 2947 は桁の数字が 2947 と,増加 → 減少 → 増加 の順になっているのでジグザグ数である.また, 71946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である.一方, 123714467144288 はジグザグ数ではない.な お, 1 桁の正の整数はジグザグ数であると考えることとする.

A 以上 B 以下の M の倍数のうち,ジグザグ 数の個数を 10000 で割った余りを求めるプログラムを作成せよ.


入力

入力は 3 行からなり, 1 行に 1 つずつ正の整数が書かれている.

1 行目の整数は A を, 2 行目の整数は B を, 3 行目の整数は M を表す.これらは 1 \leq A \leq B \leq 10^{500}1 \leq M \leq 500 を満たす.

AB の値は,通常の整数を表すデータ型には収まらない可能性があることに注意せよ.

出力

A 以上 B 以下の M の倍数のうち,ジグザグ 数の個数を 10000 で割った余りを 1 行で出力せよ.


入力例 1

100
200
5

出力例 1

13

入出力例 1 において, 100 以上 200 以下の 5 の倍数であるジグザグ数は, 105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 19513 個である.


入力例 2

6
1234567
3

出力例 2

246

入出力例 2 において, 6 以上 1234567 以下の 3 の倍数であるジグザグ数は 50246 個あるので,それを 10000 で割った余りである 246 を出力する.