Sum over Dream‐Formula Expressions

A young competitor had a strange dream of a mathematical formula – a formula containing only digits and the multiplication symbol. In his fuzzy dream he sometimes mistook the multiplication sign (×) for the letter \(x\). Miraculously, he remembered the value of \(x\) and, thinking letters could be seen as numbers, he replaced every occurrence of \(x\) with the number and computed the value of the expression. Before he was caught sleeping by his coach, he wanted to recall the number he had computed.

However, too tired to compute a single value, he decided to sum up the values of all possible substitutions. In his dream the formula was given in a blurred form: some positions are uncertain. Formally, you are given a string \(s\) consisting of digits (from 1 to 9) and question marks ?. The string satisfies that the first and last characters are digits and no two question marks are adjacent. Each ? can be independently replaced by either the letter \(x\) or the multiplication symbol \(\times\). Here the letter \(x\) is a placeholder for a given string‐variable which represents an integer when substituted. For example, if after a replacement one obtains 12x45 and if \(x=33\), then the resulting expression is interpreted as a concatenation: 123345.

Now, define the evaluation process as follows. First, for a fixed replacement pattern, interpret the resulting expression as a multiplication of several factors. Each factor is obtained by concatenating a series of fixed number tokens (which appear in \(s\)) with the variable insertion (each occurrence of \(x\)) in between. Concretely, if a factor has tokens \(a_0, a_1, \dots, a_{r-1}\), then its value is computed by concatenating the string \(a_0\), then the string representation of \(x\), then \(a_1\), then \(x\), and so on. When concatenating, the operation works as follows: if \(t\) is the string representation of \(x\) (with digit‐length \(L\)) and if a fixed token is a string of digits, then concatenation acts as appending the digits; numerically, if you have a number \(A\) and you append a string representing a number \(B\) of length \(l\), the new number is \(A \times 10^{l} + B\). When inserting \(x\) in between tokens, the effect is similar but note that the inserted value has \(L\) digits. Therefore, if a factor results from joining tokens \(a_0, a_1, \dots, a_{r-1}\) (each token is a string of digits) with each connection having an inserted \(x\), its value is a linear function of \(x\); it can be written as \(A\,x + B\), where \(A\) and \(B\) depend on the tokens and on \(L = \mathtt{len}(x)\).

For a fixed replacement pattern and a fixed \(x=k\) (with \(k\) given as an integer), denote by \(f(k)\) the sum over all replacement patterns of the value of the corresponding expression (product of factors). Since our young friend forgot the value of \(x\), he is wondering:

What is \(\sum_{i=L}^{R} f(i) \bmod (10^9+7)\)?

Input

The first line contains a non‐empty string \(s\) consisting of digits (1–9) and question marks ?, with the first and last characters being digits and no two adjacent question marks.

The second line contains two integers \(L\) and \(R\) \((1 \le L \le R \le 10^9)\), representing the inclusive range for \(x\). Here, when \(x=k\) the replacement of x by the string representation of \(k\) is performed.

Output

Output a single integer: the value of \(\sum_{k=L}^{R} f(k)\) modulo \(10^9+7\).

inputFormat

The input consists of two lines.

• The first line contains the string \(s\) (only digits 1–9 and '?' characters).
• The second line contains two integers \(L\) and \(R\) separated by a space.

outputFormat

Output a single integer – the answer modulo \(10^9+7\).

sample

12?3
1 10

1118