题目描述Description

在《金铲铲之战》中，铲铲军团有一套独特的战力评估系统。每个英雄的编号可以看作一个正整数（十进制表示，无前导零），而军团内部有 m 种技能组合，每种组合 p_i（一个数字串）对应一个战力加成 c_i。

对于一名编号为 n 的英雄，其模式代价 f(n) 定义为：将 n 的十进制字符串看作一个序列，其中所有出现的技能组合（允许重叠）的战力加成之和。同一个技能组合每出现一次，其战力加成就累加一次。

注意：输入中可能出现多个相同的技能组合，此时它们的战力加成应当累加。例如，技能组合 "12" 出现两次，加成分别为 3 和 5，则等价于一个加成 8 的技能组合 "12"。

例如，英雄编号 n = 11212，技能组合 "12" 加成 3，"2" 加成 1，则：

• "12" 出现在位置 1–2 和 3–4，贡献 3 \times 2 = 6
• "2" 出现在位置 2、4，贡献 1 \times 2 = 2

总战力加成 f(11212) = 8。

现在，铲铲军团想要评估编号区间 [l, r] 内所有英雄的总战力，即： \sum_{n=l}^{r} f(n)

请你计算这个总和，并对 10^9 + 7 取模。

输入格式Input

第一行：一个字符串 l（无前导零，除非是 "0"）
第二行：一个字符串 r（无前导零，除非是 "0"）
第三行：一个整数 m，表示模式串的数量
接下来 m 行：每行一个字符串 p_i 和一个整数 c_i，用一个空格分隔

• 模式串 p_i 仅由数字 '0'–'9' 组成
• 代价满足 1 \le c_i \le 10^9

输出格式Output

输出一个整数，表示 \sum_{n=l}^{r} f(n) 对 10^9 + 7 取模的结果。

样例Sample

提示Hint

样例解释

在编号 1 到 20 的英雄中：

• 技能组合 "12"（加成 3）仅出现在英雄 12 中一次，贡献 3；
• 技能组合 "2"（加成 1）出现在英雄 2、12、20 中，各出现一次，贡献 1 \times 3 = 3。 总战力 3 + 3 = 6。

数据范围与提示

• 1 \le |l|, |r| \le 1000
• 1 \le m \le 100
• 1 \le |p_i| \le 1000，\sum |p_i| \le 2000
• 1 \le c_i \le 10^9
• l 和 r 不含前导零（除非值为 0 本身）
• 保证 l \le r（按数值比较）
• 技能组合的匹配允许重叠。例如数字串 "111" 中，组合 "11" 会出现两次（位置 1-2 和 2-3）。
• 输入中可能出现相同的技能组合，此时它们的战力加成应累加。

出题Author

wjh

来源Source

深圳技术大学第六届程序设计竞赛