← 返回题目列表

AtCoder · s8pc_1_f

F. square1001最喜欢的回文

中文机器翻译题面 查看原题

进行了重新判断。非常抱歉。(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,d是 在 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