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

[problemUrl]: https://atcoder.jp/contests/s8pc-1/tasks/s8pc_1_f $ 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 翻译