Thay thế trong số

Ban đầu bạn có một xâu $s$ gồm các chữ số. Bạn nhận được $n$ truy vấn, mỗi truy vấn có dạng "$d_i\to t_i$", nghĩa là "thay thế tất cả chữ số $d_i$ trong $s$ bằng xâu $t_i$". Ở đây $d_i$ là một chữ số (từ 0 đến 9), còn $t_i$ là một xâu gồm các chữ số (có thể rỗng).

Các truy vấn được thực hiện lần lượt theo đúng thứ tự đã cho. Ví dụ, nếu $s=123123$ thì truy vấn "$2\to 00$" biến $s$ thành $10031003$, còn truy vấn "$3\to$" (thay 3 bằng xâu rỗng) biến nó thành $s=1212$.

Sau khi thực hiện xong tất cả truy vấn, hãy coi $s$ là một số nguyên viết ở hệ thập phân và in ra phần dư của nó khi chia cho ${10}^9+7$.

Lưu ý: khi coi $s$ là một số, các chữ số 0 ở đầu không bị loại bỏ khỏi xâu (chúng chỉ đơn giản không ảnh hưởng tới giá trị số). Nếu $s$ là xâu rỗng thì số tương ứng bằng 0.

Dữ liệu vào

• Dòng đầu chứa xâu $s$ gồm các chữ số, là xâu ban đầu trước khi xử lý.
• Dòng thứ hai chứa số nguyên $n$, số lượng truy vấn.
• $n$ dòng tiếp theo, dòng thứ $i$ mô tả truy vấn dưới dạng "$d_i\mathtt{\text{->}}{t}_i$", trong đó $d_i$ đúng một chữ số và $t_i$ là xâu gồm các chữ số ($t_i$ có thể rỗng).

Dữ liệu ra

In ra một số nguyên duy nhất: phần dư của số thu được khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le |s|\le {10}^5$
• $0\le n\le {10}^5$
• Tổng độ dài các $t_i$ trên tất cả truy vấn không vượt quá ${10}^5$.

Ví dụ