006 - ジグザグ数 (Zig-Zag Numbers)

問題

正の整数を (先頭に 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⁵⁰⁰，1 ≦ M ≦ 500 を満たす．

※ A や B の値は，通常の整数を表すデータ型には収まらない可能性があることに注意せよ．

出力

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

入出力例

100
200
5
  

6
1234567
3
  

13
   

246
   

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

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