题目背景

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

题目描述

他梦见了一个数学公式，只包含数字和乘号，梦境是迷糊的，所以他可能会把乘号看成字母 $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