第11回日本情報オリンピック　予選６

2011年12月18日
情報オリンピック日本委員会

問題

正の整数を (先頭に 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 を出力する．

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

採点用データ