Substitutes in Number

1000ms

262144K

Description:

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⁹ + 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!

Input:

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

The second line contains a single integer n (0 ≤ n ≤ 10⁵) — 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⁵. The queries are written in the order in which they need to be performed.

Output:

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

Sample Input:

123123
1
2->00

Sample Output:

10031003

Sample Input:

123123
1
3->

Sample Output:

Sample Input:

222
2
2->0
0->7

Sample Output:

Sample Input:

1000000008
0

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF464C