Digits of Number Pi

给定长度为 $n$ 的数字串 $s$ 和长度为 $d$ 的不含前导零的数字串 $x,y(x \le y)$。 求**存在长度至少为 $\left\lfloor\frac{d}{2}\right\rfloor$ 的子串是 $s$ 的子串**的数字串 $t \in [x,y]$ 的数量。 $n \le 10^3$，$d \le 50$，答案对 $10^9+7$ 取模。

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 $ 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.

Print how many numbers in the segment from $ x $ to $ y $ that are half-occurrences in $ s $ modulo $ 10^{9}+7 $ .

02
10
19

2

023456789
10
19

9

31415926535
10
29

20