AT_s8pc_1_f.square1001の好きな回文数 (square1001's Favorite Palindrome)

$ square1001 $ 的子串 “$ 1001 $” 是一个回文数。

也就是说，正因为如此，他也非常喜欢回文数。

于是，E869120 给他出了如下的问题：

“有一组数，范围是 $ a $ 到 $ b $（包含端点）。在这些数中，有多少个数既是 $ c $ 的倍数，又满足各位数字之和等于 $ d $，并且还是回文数？”

$ square1001 $ 想用普通的全枚举方法来求解，但由于 $ a $ 和 $ b $ 都非常大，所以无法实现。

请你求出这个问题的答案，并对 $ 10000 $ 取模后输出。

输入为一行，格式如下：

$ a $ $ b $ $ c $ $ d $

其中 $ a, b, c, d $ 均为正整数。

输出满足条件的回文数的个数，结果对 $ 10000 $ 取模。

限制条件

• $ a < b $
• $ 2 \leq |a| = |b| \leq 80 $，且 $ |a|,\ |b| $ 均为 $ 2 $ 的倍数
• $ 1 \leq c \leq 50 $
• $ 1 \leq d \leq 720 $
• $ a, b $ 均为回文数

其中，$ |a| $ 表示 $ a $ 的位数。

部分分

若能正确解决所有满足 $ 1 \leq a, b \leq 10,000,000,000 $ 的数据集，则可获得 20 分。

若能正确解决剩余所有数据集，则可获得 80 分。

样例解释 1

“$ 9999 $” 满足所有条件。

样例解释 2

“$ 3773 $” 满足所有条件。

样例解释 3

不存在以 $ 0 $ 结尾的回文数。
问题出题人：E869120

由 ChatGPT 4.1 翻译