F - square1001の好きな回文数 (square1001's Favorite Palindrome)

Time Limit: 4 sec / Memory Limit: 256 MB

リジャッジをしました。申し訳ございません。(01/24 22:16:18追記)

部分点のケースはあっていますが、sub2-3.txtが間違っていることが判明しました。消去し次第リジャッジを行います。(01/24 22:12:49追記)

問題文

square1001の部分文字列である「1001」は回文数である。

すなわち、その名前を付けた彼も回文数が好きであった。

ということで、E869120は彼に次のような問題を出した。

a以上b以下の数がある。 その中で、cの倍数かつ各位の数字の和が dである回文数はいくつあるか。」

square1001は、普通に全探索して求めようとしたが、 a , bが相当大きいためできなかった。

その問題の答えをmod 10000で求めよ。


入力

入力は以下の形式で標準入力から与えられる。

a b c d

正整数a,b,c,d1 行に入力される。

出力

条件を満たす回文数の個数を1行に出力せよ。

制約

  • a<b
  • 2≦|a|=|b|≦80 かつ |a|, |b|2の倍数
  • 1≦c≦50
  • 1≦d≦720
  • a,bは回文数

ここで, |a|aの桁数を表す。

部分点

1≦a,b≦10,000,000,000を満たすデータセットすべてに正解した場合は、 20点が与えられる。

残りのデータセットすべてに正解した場合、80点が与えられる。


入力例1

1001 9999 9 36

出力例1

1

9999」が条件を満たす。


入力例2

1001 4004 49 20

出力例2

1

3773」が条件を満たす。


入力例3

1000000001 9999999999 50 50

出力例3

0

0」で終わる回文数は存在しない。

問題文担当者:E869120