Substitutes in Number

### 题意 有一个由数字组成的字符串$s$和$n$条指令$d_i->t_i$。意思是用$t_i$替换所有字符串中的$d_i$。例如，如果$s=123123$，则“2→00”将把$s$转换为$10031003$，查询“3→”(用空字符串替换$3$),将$s$转换为$s=1212$。在所有的指令之后，请在十进制数等于$s$的情况下取模$mod=1000000007(10^9+7)$。 同时**需要注意，在$s$表示为十进制数时，需要忽略前导$0$；如果$s$是一个空字符串，那么就默认为$0$**。 ------- ### 输入格式 第一行，一个字符串$s(1\le\vert{s}\vert\le 10^5)$； 第二行，一个整数$n(0\le n\le 10^5)$,表示指令的条数； 第三行到第$n+2$行，每行一条指令，格式为$d_i->t_i$,其中每一个字符都是由$0-9$的数字组成。**注意，$t_i$可能为空，保证所有$t_i$的长度总和不超过$10^5$**。对于所有的指令，都是按照输入的顺序进行工作的。 ------- ### 输出格式 一个整数，**并对$1000000007(10^9+7)$取模**。 ------- ### 数据样例 **输入** ``` 123123 1 2->00 ``` **输出** ``` 10031003 ```

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 (10^{9}+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!

The first line contains string $ s $ ( $ 1<=|s|<=10^{5} $ ), consisting of digits — the string before processing all the requests. The second line contains a single integer $ n $ ( $ 0<=n<=10^{5} $ ) — 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 $ 10^{5} $ . The queries are written in the order in which they need to be performed.

Print a single integer — remainder of division of the resulting number by $ 1000000007 (10^{9}+7) $ .

123123
1
2->00

10031003

123123
1
3->

1212

222
2
2->0
0->7

777

1000000008
0

1

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