Link my group on LQDOJ

Nguồn: Apex Cup 2026 in ledinhbaonam group(here: ledinhbaonam group)

Trong kỳ thi HSG Quốc gia, một số nguyên dương \(X\) được gọi là Số lập dị bậc \(K\) (\(0 \le K \le 9\)) nếu như trong biểu diễn thập phân của \(X\):

1. Tần suất xuất hiện của chữ số \(K\) lớn hơn hẳn tổng tần suất xuất hiện của tất cả các chữ số khác cộng lại.
2. Đồng thời, biểu diễn thập phân của \(X\) không chứa bất kỳ chuỗi con liên tiếp nào trùng với một trong các chuỗi cấm cho trước thuộc tập \(S = \{s_1, s_2, \dots, s_M\}\)

Ban tổ chức đưa ra \(Q\) truy vấn, mỗi truy vấn gồm một bộ ba \((K, L, R)\). Bạn hãy tính số lượng Số lập dị bậc \(K\) nằm trong đoạn \([L, R]\). Vì số lượng kết quả có thể rất lớn, hãy in ra kết quả theo dư cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên \(M\) (\(0 \le M \le 100\)) — số lượng chuỗi cấm.
• \(M\) dòng tiếp theo, mỗi dòng chứa một xâu ký tự chỉ gồm các chữ số 0 đến 9 đại diện cho xâu \(s_i\) (\(\sum \vert{}s_i\vert{} \le 500\)).
• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)) — số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(K, L, R\) (\(0 \le K \le 9, 1 \le L \le R \le 10^{18}\)).

Output

• Ghi ra \(Q\) dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng lấy dư theo \(10^9 + 7\).

Example

2
13
222
2
2 1 25
2 200 225

2
7