Bạn được cho 1 xâu ~s~ độ dài ~N~ (1 ≤ ~N~ ≤ 1000) chỉ gồm các kí tự "?" và chữ cái in hoa. Bạn cũng đồng thời được cho ~M~ xâu ~t_i~ (1 ≤~ M~ ≤ 100). Mỗi xâu ~t_i~ có độ dài không vượt quá 20 và chỉ chứa các chữ cái in hoa.

Bạn có thể thay các kí tự "?" trong xâu ~s~ thành một trong các chữ cái in hoa từ "A" đến "Z". Giá trị của một lần thay như thế là số lần xuất hiện của ~M~ xâu ~t_i~ đã cho trong xâu ~s~. Lưu ý rằng mỗi xâu ~t_i~ có thể xuất hiện trong xâu ~s~ nhiều lần.

Gọi ~cntQ~ là số lượng kí tự "?" trong xâu ~s~ ban đầu của chúng ta. Như các bạn đã biết, có tổng cộng ~26^{cntQ}~ cách thay các kí tự "?" trong xâu ~s~ ban đầu.

Nhiệm vụ của bạn là hãy tính tổng giá trị của ~26^{cntQ}~ cách thay các kí tự "?" trong xâu ~s~ ban đầu.

Lưu ý: Do kết quả có thể rất lớn, bạn hãy lấy kết quả mod cho ~10^9~ +7.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên ~N~ (1 ≤ ~N~ ≤ 1000) — Độ dài của xâu ~s~.
• Dòng thứ hai gồm một xâu ~s~ độ dài ~N~ là xâu ban đầu của mình.
• Dòng tiếp theo gồm một số nguyên ~M~ (1 ≤ ~M~ ≤ 100) — Số lượng các xâu được cho
• ~M~ Dòng tiếp theo, dòng thứ ~i~ gồm một xâu ~t_i~, độ dài xâu không vượt quá 20.

Kết quả

• In ra một số nguyên duy nhất là kết quả tính được.

Ví dụ

Sample Input 1

5
ABCAB
3
ABC
AB
A

Sample Output 1

5

Sample Input 2

4 
?AB?
1
AB

Sample Output 2

676

Sample Input 3

10
??????????
3
BA
AB
A

Sample Output 3

923545757

Sample Input 4

10
??????????
3
ABC
AB
A

Sample Output 4

734458686

Giới hạn

• Subtask 1 (20% số test): ~N~ ≤ ~10,M~ ≤ 10, trong ~M~ xâu ~t_i~ chỉ có 2 loại chữ cái A và B.Độ dài các xâu ~t_i~ không quá 10.
• Subtask 2 (30% số test): ~N~ ≤ ~100,M~ ≤ 10, trong ~M~ xâu ~t_i~ chỉ có 2 loại chữ cái A và B.Độ dài các xâu ~t_i~ không quá 10.
• Subtask 3 (50% số test): không có ràng buộc gì thêm.

Giải thích

• Ở ví dụ 1, xâu "ABC" xuất hiện 1 lần, xâu "AB" xuất hiện 2 lần, xâu "A" xuất hiện 2 lần. Nên tổng giá trị là 1 + 2 + 2 = 5
• Ở ví dụ 2, có ~26^2~ các cách thay các kí tự "?" thành các chữ cái in hoa. Ở mỗi cách thay, xâu "AB" xuất hiện 1 lần. Nên tổng giá trị là ~26^2~ *1 = 676

Nguồn: Free Contest