/ 
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき，その数は「ジグザグ数」であると呼ぶことにしよう．たとえば，2947 は桁の数字が 2 → 9 → 4 → 7 と，増加 → 減少 → 増加 の順になっているのでジグザグ数である．また，71\,946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である．一方，123 や 71\,446 や 71\,442 や 88 はジグザグ数ではない．なお，1 桁の正の整数はジグザグ数であると考えることとする．
A 以上 B 以下の M の倍数のうち，ジグザグ数の個数を 10\,000 で割った余りを求めるプログラムを作成せよ．
入力
入力は 3 行からなり，1 行に 1 つずつ正の整数が書かれている．
1 行目の整数は A を，2 行目の整数は B を，3 行目の整数は M を表す．これらは 1 \leqq A \leqq B \leqq 10^{500} ，1 \leqq M \leqq 500 を満たす．
※ A や B の値は，通常の整数を表すデータ型には収まらない可能性があることに注意せよ．
出力
A 以上 B 以下の M の倍数のうち，ジグザグ数の個数を 10\,000 で割った余りを 1 行で出力せよ．
入力例 1
100 200 5
出力例 1
13
入出力例 1 において，100 以上 200 以下の 5 の倍数であるジグザグ数は，105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195 の 13 個である．
入力例 2
6 1234567 3
出力例 2
246
入出力例 2 において，6 以上 1\,234\,567 以下の 3 の倍数であるジグザグ数は 50\,246 個あるので，それを 10\,000 で割った余りである 246 を出力する．