Bạn có được một tài liệu mật của nước IOI, được viết bằng các chữ cái từ A đến Z. Bản gốc của tài liệu được viết bằng ngôn ngữ IOI. Có thể thu được bản gốc bằng cách xóa một số ký tự trong tài liệu mật, có thể không xóa ký tự nào.

Một câu trong ngôn ngữ IOI là một chuỗi có ít nhất một ký tự, thỏa mãn \(M\) quy tắc đôi một khác nhau. Quy tắc thứ \(i\) \((1\le i\le M)\) quy định rằng ký tự \(B_i\) không được xuất hiện ngay sau ký tự \(A_i\).

Yêu cầu

Tính số bản gốc có thể có của tài liệu mật, lấy phần dư khi chia cho \(10\,000\,000\). Nếu những cách xóa khác nhau tạo ra cùng một chuỗi bản gốc thì chỉ tính chuỗi đó một lần.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(L\), là độ dài của tài liệu mật.
• Dòng thứ hai chứa chuỗi tài liệu mật gồm \(L\) chữ cái từ A đến Z.
• Dòng thứ ba chứa số nguyên \(M\), là số quy tắc của ngôn ngữ IOI.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i+3\) \((1\le i\le M)\) chứa hai chữ cái \(A_i,B_i\) từ A đến Z, cách nhau bởi một dấu cách, mô tả quy tắc thứ \(i\). Không tồn tại \(j\ne i\) sao cho đồng thời \(A_j=A_i\) và \(B_j=B_i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số bản gốc có thể có, lấy phần dư khi chia cho \(10\,000\,000\).

Ràng buộc

• \(1\le L\le300\,000\).
• \(0\le M\le26\times26\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(0{,}5\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm. Các điều kiện về tỷ lệ điểm dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(L\le15\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(L\le5\,000\).

Ví dụ

5
JOIOI
1
I O

15

26
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0

7108863