Ngôn ngữ ab là ngôn ngữ chỉ dùng hai chữ cái '~a~' và '~b~' để tạo các văn bản. Trong ngôn ngữ này người ta dùng một tập từ vựng, mỗi từ tương ứng với một xâu chỉ gồm các chữ cái '~a~' và '~b~' và quy định một số từ không thể đứng liền nhau để đọc các văn bản.

Cho một văn bản trong ngôn ngữ này tương ứng với một xâu ~S~ có độ dài ~N~ chỉ gồm các chữ cái '~a~' và '~b~', một tập gồm ~M~ từ vựng đánh số từ ~1~ đến ~M~ và ~K~ cặp từ không thể đứng liền nhau.

Một cách đọc xâu ~S~ là cách chia xâu ~S~ thành các xâu con gồm các kí tự liên tiếp sao cho mỗi xâu con tương ứng với một từ trong tập ~M~ từ vựng đã cho. Nếu trong một cách đọc có một cặp từ vi phạm tính không đứng liền nhau thì cách đọc đó là không hợp lệ.

Yêu cầu: Hãy tìm số lần xuất hiện của mỗi từ vựng trong các cách đọc hợp lệ có thể có của ~S~. Biết rằng trong một cách đọc hợp lệ, một từ có thể xuất hiện nhiều lần, tất cả các lần xuất hiện đó đều được tính trong kết quả.

Input

Vào từ file văn bản ABLANG.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(1\leq N\leq 50000, 1\leq M\leq 50, 1\leq K\leq 255)~.
• Dòng thứ hai chứa xâu ~S~ chỉ gồm các chữ cái '~a~' và '~b~'.
• ~M~ dòng tiếp theo mỗi dòng chứa một từ vựng, tương ứng như một xâu chỉ gồm các chữ cái '~a~' và '~b~'. Không có hai từ nào trùng nhau và có độ dài không vượt quá độ dài xâu ~S~.
• ~K~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~i, j~ ~(1\leq i, j\leq M)~ cách nhau dấu cách với nghĩa là từ ~i~ và từ ~j~ không được đứng liền nhau theo thứ tự ~i~ trước ~j~ sau tính từ trái sang trong xâu ~S~. Có thể có trường hợp ~i = j~.

Các số trên một dòng cách nhau một dấu cách.

Output

Ghi ra file văn bản ABLANG.OUT: Tương ứng với mỗi từ theo thứ tự từ tệp dữ liệu vào ghi ra một số là phần dư của phép chia số lần xuất hiện từ đó trong các cách đọc hợp lệ cho ~10^9+7~.

Scoring

• Subtask ~1~ ~(20\%)~: ~K=0, S~ và các từ chỉ gồm chữ cái '~a~'.
• Subtask ~2~ ~(22\%)~: Chỉ có một cách đọc đúng và tất cả các từ có độ dài khoảng ~100~.
• Subtask ~3~ ~(13\%)~: Chỉ có một cách đọc đúng.
• Subtask ~4~ ~(10\%)~: ~K=0~ và tất cả các từ có độ dài không quá ~100~.
• Subtask ~5~ ~(13\%)~: Tất cả các từ có độ dài không quá ~100~.
• Subtask ~6~ ~(22\%)~: Không còn ràng buộc gì thêm.

Example input 1

6 3 0
aabaaa
aab
aaa
aba

Example output 1

1
1
0

Note 1

Chỉ có một cách đọc và hợp lệ: ~aab | aaa~.

Từ thứ nhất xuất hiện ~1~ lần.

Từ thứ hai xuất hiện ~1~ lần.

Từ thứ ba không xuất hiện lần nào.

Example input 2

14 5 1
baabaaababbbbb
bbbb
a
abab
baa
ba
4 3

Example output 2

2
3
2
1
3

Note 2

Có bốn cách đọc:

1. ~baa|ba|a|abab|bbbb~
2. ~baa|baa|abab|bbbb~
3. ~ba|a|baa|abab|bbbb~
4. ~ba|a|ba|a|abab|bbbb~

Các cách đọc ~2, 3~ không hợp lệ bởi hai từ ~4, 3~ đừng liền nhau.