Thay thế chữ số

Điểm: 7,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một xâu $s$ gồm các chữ số. Lần lượt thực hiện $n$ truy vấn có dạng " $d \to t$ ", nghĩa là thay tất cả các chữ số $d$ trong $s$ bằng xâu $t$ (xâu $t$ có thể rỗng — khi đó mọi chữ số $d$ đều bị xóa). Các truy vấn được thực hiện đúng theo thứ tự đã cho.

Sau khi áp dụng toàn bộ truy vấn, hãy xem $s$ như biểu diễn thập phân của một số nguyên (bỏ qua các chữ số $0$ ở đầu, và xâu rỗng được coi là số $0$ ), rồi in ra phần dư của số đó khi chia cho $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu chứa xâu $s$ gồm các chữ số.
Dòng thứ hai chứa số nguyên $n$ — số lượng truy vấn.
$n$ dòng tiếp theo, mỗi dòng có dạng d->t, trong đó $d$ là đúng một chữ số (từ $0$ đến $9$ ) và $t$ là xâu gồm các chữ số (có thể rỗng).

Dữ liệu ra

Một số nguyên duy nhất — kết quả mod $10^{9} + 7$ .

Ràng buộc

$1 \leq | s | \leq 10^{5}$ .
$0 \leq n \leq 10^{5}$ .
Tổng độ dài các xâu $t$ trên toàn bộ truy vấn không vượt quá $10^{5}$ .

Ví dụ

Input	Output	Giải thích
123123 1 2->00	10031003	Sau khi thay mọi chữ số 2 bằng "00", xâu trở thành "10031003".
123123 1 3->	1212	Xóa mọi chữ số 3, còn lại "1212".
222 2 2->0 0->7	777	Bước 1: "222" → "000". Bước 2: "000" → "777". Lưu ý các chữ số 0 ở đầu vẫn được tiếp tục thay thế.
1000000008 0	1	Không có truy vấn nào; $1000000008 mod (10^{9} + 7) = 1$ .

Bình luận

Không có bình luận tại thời điểm này.