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