C. Замены в числе
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Андрей и Женя играют в игру. В начале у Андрея есть строка s, состоящая из цифр. Женя несколько раз дает Андрею запросы вида «di → ti», что означает «замени все цифры di в строке s на подстроки, равные ti». Например, при s = 123123 после запроса «2 → 00» s станет равно 10031003, а после запроса «3 → » («замени 3 на пустую строку») s = 1212. После всех запросов Женя просит Андрея сообщить ему остаток от деления числа, десятичная запись которого совпадает со строкой s, на 1000000007 (109 + 7). При представлении s в виде десятичного числа ведущие нули следует игнорировать; если s — пустая строка, считается, что число равно нулю.

Андрею надоело обрабатывать запросы Жени вручную, и он попросил вас написать программу для этой цели. Помогите ему!

Входные данные

В первой строке записана строка s (1 ≤ |s| ≤ 105), состоящая из цифр — строка до выполнения всех запросов.

Во второй строке записано целое число n (0 ≤ n ≤ 105) — количество запросов.

В следующих n строках заданы описания запросов: i-й запрос описывается строкой вида «di->ti», где di — ровно одна цифра (от 0 до 9), ti — строка, состоящая из цифр (ti может быть пустой строкой). Сумма длин строк ti для всех запросов не превосходит 105. Запросы записаны в том порядке, в котором их следует выполнять.

Выходные данные

Выведите целое число — остаток от деления итогового числа на 1000000007 (109 + 7).

Примеры
Входные данные
123123
1
2->00
Выходные данные
10031003
Входные данные
123123
1
3->
Выходные данные
1212
Входные данные
222
2
2->0
0->7
Выходные данные
777
Входные данные
1000000008
0
Выходные данные
1
Примечание

Обратите внимание, что ведущие нули не удаляются из строки s после выполнения замены (это отражено в третьем примере).