Thay thế chữ số

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\le |s|\le {10}^5$.
• $0\le n\le {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ụ