CF464C.Substitutes in Number

Andrew and Eugene are playing a game. Initially, Andrew has string s, consisting of digits. Eugene sends Andrew multiple queries of type "d__i → t__i", that means "replace all digits d__i in string s with substrings equal to t__i". For example, if s = 123123, then query "2 → 00" transforms s to 10031003, and query "3 → " ("replace 3 by an empty string") transforms it to s = 1212. After all the queries Eugene asks Andrew to find the remainder after division of number with decimal representation equal to s by 1000000007 (109 + 7). When you represent s as a decimal number, please ignore the leading zeroes; also if s is an empty string, then it's assumed that the number equals to zero.

Andrew got tired of processing Eugene's requests manually and he asked you to write a program for that. Help him!

安德鲁和叶甫根尼正在玩一个游戏。初始时，安德鲁拥有一个由数字组成的字符串 $s$。叶甫根尼向安德鲁发送多个形如 “$d_i \to t_i$” 的查询，其含义为：“将字符串 $s$ 中所有数字 $d_i$ 替换为子串 $t_i$”。例如，若 $s = 123123$，则查询 “$2 \to 00$” 将 $s$ 变为 $10031003$；而查询 “$3 \to $”（即“将 $3$ 替换为空字符串”）将 $s$ 变为 $1212$。在执行完所有查询后，叶甫根尼要求安德鲁求出：将最终字符串 $s$ 视作十进制数时，该数对 $1000000007$（即 $10^9 + 7$）取模所得的余数。注意：将 $s$ 解释为十进制数时，应忽略前导零；若 $s$ 为空字符串，则视其表示的数为 $0$。

安德鲁已厌倦手动处理叶甫根尼的请求，于是请你编写一个程序来完成这项任务。请帮助他！

The first line contains string s (1 ≤ |s| ≤ 105), consisting of digits — the string before processing all the requests.

The second line contains a single integer n (0 ≤ n ≤ 105) — the number of queries.

The next n lines contain the descriptions of the queries. The i-th query is described by string "d__i->t__i", where d__i is exactly one digit (from 0 to 9), t__i is a string consisting of digits (t__i can be an empty string). The sum of lengths of t__i for all queries doesn't exceed 105. The queries are written in the order in which they need to be performed.

第一行包含一个字符串 $s$（$1 \leq |s| \leq 10^5$），由数字组成——即所有操作前的原始字符串。

第二行包含一个整数 $n$（$0 \leq n \leq 10^5$）——查询的数量。

接下来的 $n$ 行描述了这些查询。第 $i$ 个查询由字符串 "$d_i\rightarrow t_i$" 描述，其中 $d_i$ 是恰好一位数字（从 0 到 9），$t_i$ 是一个由数字组成的字符串（$t_i$ 可以为空字符串）。所有查询中 $t_i$ 的长度之和不超过 $10^5$。查询按需执行的顺序给出。

Print a single integer — remainder of division of the resulting number by 1000000007 (109 + 7).

输出一个整数——结果数对 1000000007（$10^9 + 7$）取模的余数。

Note that the leading zeroes are not removed from string s after the replacement (you can see it in the third sample).

注意，替换后字符串 s 中的前导零不会被删除（可在第三个样例中看到）。