問題

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