P10167 [DTCPC 2024] Xiao Fang Learns Multiplication

Xiao Fang was in a math class and started learning multiplication, but he fell asleep in class.

He dreamed of a math formula that only contained digits and multiplication signs. Because the dream was blurry, he might have mistaken the multiplication sign for the letter $x$. Somehow he remembered the value of this $x$, and he believed that letters can be treated as digits. So, after replacing all letters $x$ with digits, he computed the value of the expression. Then he was caught sleeping by the coach. Before being ganked, he wanted to recall the value he computed in the dream. But Xiao Fang was too sleepy, so he decided to compute the value in all cases: that is, for each **multiplication sign**, replace it or do not replace it with the value represented by the letter $x$, and sum the values over all possible cases. However, Xiao Fang even forgot $x$ itself. He only remembers that it is within some range $[L,R]$, so for each $x$ he needs to compute the sum described above, and then sum those results again. Xiao Fang just learned multiplication and cannot handle very large numbers, so he wants you to output the answer $\bmod {10^9+7}$. **Formal statement** You are given a string $s$ that contains only digits $1 \sim 9$ and `?`. It is guaranteed that there are no two adjacent `?`, and the first and last characters of the string are not `?`. Now each `?` can be replaced by $x$ or $\times$, where $x$ is a given string-concatenation variable. For example, for `12x45`, when $x=33$, the replacement result is `123345`. Let the sum of the weights of the expression over all replacement schemes of `?` when $x=k$ be $f(k)$. Compute $\sum_{i=L}^R{f(i)} \bmod {10^9 + 7}$.

The first line contains a string $S$ of length $n$ ($1 \le n \le 2000$), representing the expression. The second line contains two positive integers $L,R$ ($1 \le L \le R < 10^{18}$).

Output one positive integer, the answer modulo $10^9+7$.

Translated by ChatGPT 5