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

時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
8sec
MLE
256MB
得点
100

問題

正の整数を (先頭に 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 ≦ 10500,1 ≦ M ≦ 500 を満たす.

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

出力

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

入出力例


入力例 1 入力例 2
100
200
5
  
6
1234567
3
  
 
出力例 1 出力例 2
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 を出力する.