CF585F Digits of Number Pi

Vasily 最近了解到数字 $π$ 的神奇性质。在一篇文章中有人提出假说：无论我们有什么数字序列，在某个位置，这个序列都会出现在 $π$ 的小数位中。因此，如果你把著名俄国作家列夫·托尔斯泰的史诗小说《战争与和平》用数字编码，那么在 $π$ 的数字序列中就可以找到这部小说。 Vasily 为此感到无比兴奋，因为这意味着所有的书、歌曲和程序，都已经写好并被编码在 $π$ 的数字序列中了。Vasily 当然也意识到这只是个假说，还没被严格证明，于是他决定亲自验证。 为此，他从网上下载了$π$的某一位开始后的一段数字序列，并开始检查各种数字串是否出现在已下载的序列中。很快，他就找到了许多较短的数字串，但每次当字符串长度变长时，他发现这些长串并不出现在序列中。于是他做了如下定义：长度为 $d$ 的串，如果它包含长度至少为 $\lfloor \frac{d}{2} \rfloor$ 的某个子串，并且这个子串在已下载的序列中出现过，则称为 “半出现（half-occurrence）”。 为了完成调查，Vasily 选了两个长度相同且没有前导零的大整数 $x,y$（$x \leq y$），现在他想要找出区间 $[x, y]$ 内有多少个数是 $s$ 的半出现串。请你帮他计算该值，答案对 $10^9+7$ 取模。

第一行包含一个由十进制数字构成的字符串 $s$（$1 \leq |s| \leq 1000$），Vasily 将用它来匹配子串。 第二行和第三行各包含一个正整数 $x,y$，它们的长度相同，且 $x\leq y$，$2\leq d\leq 50$，且没有前导零。

输出区间 $[x, y]$ 内有多少个数字是 $s$ 的半出现串，对 $10^9+7$ 取模。

由 ChatGPT 5 翻译。