← 返回题目列表

Codeforces · 464/C

C. 替补人数

中文机器翻译题面 查看原题

安德鲁和尤金正在玩游戏。最初,Andrew 有一个由数字组成的字符串 s。 Eugene 向 Andrew 发送了多个“di → ti”类型的查询,这意味着“将字符串 s 中的所有数字 di 替换为等于 ti 的子字符串”。例如,如果 s = 123123,则查询“2 → 00”会将 s 转换为 10031003,而查询“3 →”(“将 3 替换为空字符串”)会将其转换为 s = 1212。​​在所有查询之后,尤金要求 Andrew 求出等于 s 的十进制表示形式的数字除以 1000000007 (109 + 7) 后的余数。当您将 s 表示为十进制数时,请忽略前导零;另外,如果 s 是空字符串,则假定该数字等于零。

Andrew 厌倦了手动处理 Eugene 的请求,他要求你为此编写一个程序。帮助他!

输入

第一行包含字符串 s (1 ≤ |s| ≤ 105),由数字组成 - 处理所有请求之前的字符串。

第二行包含一个整数 n (0 ≤ n ≤ 105) — 查询数。

接下来的 n 行包含查询的描述。第 i 个查询由字符串“di->ti”描述,其中 di 恰好是一位数字(从 0 到 9),ti 是由数字组成的字符串(ti 可以是空字符串)。所有查询的 ti 长度总和不超过 105。查询按照需要执行的顺序编写。

输出

打印单个整数 — 结果数除以 1000000007 (109 + 7) 的余数。

示例

输入 #1

123123
1
2->00

输出 #1

10031003

输入 #2

123123
1
3->

输出 #2

1212

输入 #3

222
2
2->0
0->7

输出 #3

777

输入#4

1000000008
0

输出#4

1

注意

请注意,替换后,前导零不会从字符串 s 中删除(您可以在第三个示例中看到它)。