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!

Input

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.

Output

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

Note

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