[DTCPC 2024] 小方学乘法

小方上数学课，开始学乘法，但是他在课上睡着了。

他梦见了一个数学公式，只包含数字和乘号，梦境是迷糊的，所以他可能会把乘号看成字母 $x$。 他冥冥之中记得这个 $x$ 的值，并且他认为字母可以看成数字，因此他在将字母 $x$ 都替换为了数字的情况下算出了这个表达式的值。 然后他被教练抓到睡觉了。 在被 gank 之前，他想回忆起梦中算出的值。 但是小方太困了，所以他决定求出所有情况下的值，也就是将每个**乘号**都替换或者不替换为字母 $x$ 所代表的值后，对所有可能情况求和。 然而小方连 $x$ 都忘记了，只记得它在某个范围 $[L,R]$ 内，所以他要对每个 $x$ 求出上面那个和的和。 小方刚学乘法，算不清太大的数字，所以他想让你求出答案 $\bmod {10^9+7}$ 的结果。 **形式化题意** 给你一个只含有数字 $1 \sim 9$ 和 `?` 的字符串 $s$，保证没有两个相邻的 `?`，且字符串的第一个字符和最后一个字符都不是 `?`。 现在每个 `?` 可以换成 $x$ 或者 $\times$，其中 $x$ 是一个给定的字符串拼接变量。 比如 `12x45` 当 $x=33$ 时替换结果为 `123345`。 记 $x=k$ 时所有 `?` 替换方案下表达式的权值和为 $f(k)$。 求 $\sum_{i=L}^R{f(i)} \bmod {10^9 + 7}$。

第一行一个长度为 $n$（$1 \le n \le 2000$） 字符串 $S$，表示算式。 第二行两个正整数 $L,R$（$1 \le L \le R < 10^{18}$）。

一行一个正整数，表示答案对 $10^9+7$ 取模后的结果。

123?13?23
1 10

507086689