C. Тоо орлуулах

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эндрю Эвгэний нар тоглоом тоглож байна. Эндрюд анх цифрүүдээс тогтсон $s$ тэмдэгт мѳр байлаа. Эвгэний Эндрю рүү "$d_{i} -> t_{i}$" хэлбэртэй хүсэлтүүд явуулах ба энэ нь "$s$ тэмдэгт мѳрний $d_{i}$ цифрүүдийг $t_{i}$ тэмдэгт мѳрѳѳр соль" гэсэн утгатай. Жишээлбэл, $s = 123123$, хүсэлт нь "$2 -> 00$" байсан бол $s$ нь $10031003$, хүсэлт нь "$3 -> $" ("3 цифрүүдийг хоосон тэмдэгт мѳрѳѳр соль") байсан бол $s = 1212$ болж хувирна. Эвгэнийгийн эдгээр хүсэлтүүдийн дараа Эндрю $s$ тоог $1000000007 (10^{9} + 7)$ тоонд хуваахад гарах үлдэгдлийг олно. $s$ тоог аравтын тоо руу шилжүүлэхдээ тэгээр эхэлсэн бол эхний тэгүүдийг орхино уу, бас $s$ нь хоосон тэмдэгт мѳр байвал тэг гэж үзнэ үү.

Эндрю Эвгэнийгийн хүсэлтийг гараар гүйцэтгэсээр ядарч байгаа тул програм бичиж ѳгѳхийг хүсчээ. Түүнд тусална уу!

Оролт

Эхний мѳр $s$ ($1 ≤ |s| ≤ 10^{5}$) тэмдэгт мѳрийг агуулна.

Хоёрдугаар мѳрѳнд хүсэлтүүдийн тоо $n$ ($0 ≤ n ≤ 10^{5}$) байрлана.

Дараагийн $n$ мѳрѳнд хүсэлтүүд байрлана. $i$-р хүсэлт "$d_{i}->t_{i}$" хэлбэртэй, энд $d_{i}$ нь яг нэг цифр (0-ээс 9 хүртэл), $t_{i}$ нь цифрүүдээс бүрдсэн тэмдэгт мѳр байна ($t_{i}$ нь хоосон байж болно). $t_{i}$ тэмдэгт мѳрүүдийн уртуудын нийлбэр $10^{5}$ тооноос хэтрэхгүй. Хүсэлтүүд нь гүйцэтгэх дарааллаараа ѳгѳгднѳ.

Гаралт

Сүүлд үүссэн тоог $1000000007 (10^{9} + 7)$ тоонд хуваахад гарах үлдэгдол болох ганц бүхэл тоог хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
123123
1
2->00
Гаралт
10031003
Оролт
123123
1
3->
Гаралт
1212
Оролт
222
2
2->0
0->7
Гаралт
777
Оролт
1000000008
0
Гаралт
1

Тэмдэглэл

$s$ тэмдэгт мѳрийн эхэнд байгаа тэгүүдийг хүсэлтүүдийг дуустал хэвээр байлгана (гуравдугаар жишээнээс харна уу).

Сэтгэгдлүүдийг ачааллаж байна...