A9626. 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 (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)$ .

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