安德鲁和尤金正在玩游戏。最初,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 中删除(您可以在第三个示例中看到它)。