← 返回题目列表

Codeforces · 585/F

F. 数字 Pi 的位数

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

Vasily 最近了解了数字 π 的惊人特性。在一篇文章中,有人假设,无论我们有什么数字序列,在某个位置,这个序列都可以在数字 π 的数字中找到。因此,如果你以俄罗斯著名作家列夫·托尔斯泰的史诗小说《战争与和平》为例,用数字对其进行编码,那么我们就会在数字π的字符中找到这部小说。

瓦西里对此非常高兴,因为这意味着所有的书籍、歌曲和程序都已经用 π 的数字编写和编码了。瓦西里当然有些警惕,这只是一个假设,还没有得到证实,所以他决定去验证一下。

为此,瓦西里从互联网上下载了包含数字 π 的数字序列的档案,从某个位置开始,并开始检查下载的档案中是否存在不同的数字串。瓦西里很快就找到了较短的数字串,但每次他取出较长的字符串时,结果发现它并不在档案中。 Vasily 提出了一个定义,如果长度为 d 的字符串包含长度至少为 $$\left\lfloor \frac{d}{2} \right\rfloor$$ 的子字符串(该子字符串出现在存档中),则该字符串是半出现的。

为了完成调查,Vasily 取了 2 个位数相同的大数 x, y (x ≤ y),现在他想找出从 x 到 y 的区间内有多少个数字,这些数字在档案中出现了一半。帮助瓦西里计算这个值对 109 + 7 的模。

输入

第一行包含由十进制数字 (1 ≤ |s| ≤ 1000) 组成的字符串 s,Vasily 将使用它来搜索子字符串。根据假设,这个数字序列确实出现在 π 的十进制表示形式中,尽管我们不能保证这一点。

第二行和第三行包含两个长度相同的正整数 x, y (x ≤ y, 2 ≤ d ≤ 50)。数字 x、y 不包含前导零。

输出

打印从 x 到 y 的段中有多少个数字在 s 模 109 + 7 中出现了一半。

示例

输入 #1

02
10
19

输出 #1

2

输入 #2

023456789
10
19

输出 #2

9

输入 #3

31415926535
10
29

输出 #3

20