CF585F.Digits of Number Pi

Vasily has recently learned about the amazing properties of number π. In one of the articles it has been hypothesized that, whatever the sequence of numbers we have, in some position, this sequence is found among the digits of number π. Thus, if you take, for example, the epic novel "War and Peace" of famous Russian author Leo Tolstoy, and encode it with numbers, then we will find the novel among the characters of number π.

Vasily was absolutely delighted with this, because it means that all the books, songs and programs have already been written and encoded in the digits of π. Vasily is, of course, a bit wary that this is only a hypothesis and it hasn't been proved, so he decided to check it out.

To do this, Vasily downloaded from the Internet the archive with the sequence of digits of number π, starting with a certain position, and began to check the different strings of digits on the presence in the downloaded archive. Vasily quickly found short strings of digits, but each time he took a longer string, it turned out that it is not in the archive. Vasily came up with a definition that a string of length d is a half-occurrence if it contains a substring of length of at least , which occurs in the archive.

To complete the investigation, Vasily took 2 large numbers x, y (x ≤ y) with the same number of digits and now he wants to find the number of numbers in the interval from x to y, which are half-occurrences in the archive. Help Vasily calculate this value modulo 109 + 7.

瓦西里最近了解了圆周率 π 的奇妙性质。在某篇文章中提出了一种假设：对于任意一个数字序列，总能在 π 的小数展开式中的某个位置找到该序列。例如，如果我们取俄国著名作家列夫·托尔斯泰的史诗巨著《战争与和平》，并将其用数字编码，那么这段编码后的数字串就必然出现在 π 的各位数字之中。

瓦西里对此欣喜若狂，因为这意味着所有书籍、歌曲和程序实际上早已被“书写”并“编码”在 π 的各位数字之中了。当然，瓦西里也略感谨慎——毕竟这仅仅是一个尚未被证明的假设。因此，他决定亲自验证一下。

为此，瓦西里从互联网上下载了一个存档文件，其中包含从 π 的某一位开始的一段连续数字序列，并开始检验各种数字字符串是否在该存档中出现。瓦西里很快找到了许多较短的数字串，但每次当他尝试更长的字符串时，却发现它并不在存档中。于是瓦西里提出了如下定义：一个长度为 $ d $ 的字符串被称为半出现（half-occurrence），当且仅当它包含一个长度至少为 的子串，且该子串在存档中出现。

为了完成这项研究，瓦西里选取了两个位数相同的大整数 $ x $、$ y $（满足 $ x \leq y $），现在他希望计算区间 $ [x, y] $ 中有多少个整数是该存档中的半出现。请帮助瓦西里计算该数值对 $ 10^9 + 7 $ 取模的结果。

The first line contains string s consisting of decimal digits (1 ≤ |s| ≤ 1000) that Vasily will use to search substrings in. According to hypothesis, this sequence of digis indeed occurs in the decimal representation of π, although we can't guarantee that.

The second and third lines contain two positive integers x, y of the same length d (x ≤ y, 2 ≤ d ≤ 50). Numbers x, y do not contain leading zeroes.

第一行包含一个由十进制数字组成的字符串 $s$（$1 \leq |s| \leq 1000$），瓦西里将用它来搜索子串。根据该假设，该数字序列确实出现在 $\pi$ 的十进制表示中，但我们无法保证这一点。

第二行和第三行分别包含两个长度均为 $d$ 的正整数 $x$ 和 $y$（满足 $x \leq y$，且 $2 \leq d \leq 50$）。数字 $x$ 和 $y$ 均不含前导零。

Print how many numbers in the segment from x to y that are half-occurrences in s modulo 109 + 7.

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