PK là một nhà du hành vũ trụ đến một hành tinh xa và thấy ngôn ngữ của người sống trên hành tinh đó rất thú vị. Ngôn ngữ này chỉ có các chữ cái là chữ cái tiếng Anh viết thường và dựa trên một quy tắc đơn giản rằng chỉ có một số chữ cái nhất định được đứng sau một chữ cái cụ thể nào đó. PK đang muốn tính xem ngôn ngữ đó có bao nhiêu từ độ dài L và kết thúc bởi chữ cái C (dữ liệu vào). Hãy giúp PK tính con số đó.
Input:
Input bắt đầu với 26 dòng, mỗi dòng chứa 26 số nguyên cách nhau bởi dấu cách. Các số nguyên đó có giá trị là 0 hoặc 1. Số thứ j tại hàng i quy định xem chữ cái thứ j trong bảng chữ cái tiếng Anh có thể đứng liền sau chữ cái thứ i trong bảng chữ cái hay không (1 nghĩa là có thể, 0 nghĩa là không thể).
Dòng tiếp theo chứa một số nguyên T, là số test case.
Cuối cùng là T dòng, mỗi dòng chứa một chữ cái C và một số nguyên L.
Output:
Với mỗi test case, hãy in ra tổng số từ có độ dài L và kết thúc bằng chữ cái C. Đáp số cho mỗi test case cần nằm trên một dòng.
Kết quả có thể rất lớn, do đó thay vì in giá trị, hãy in ra đồng dư của nó cho 1000000007.
Ràng buộc: 1 <= T <= 100
C là chữ cái tiếng Anh viết thường.
2 <= L <= 10000000
| Sample Input | Sample Output |
|---|---|
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 c 3 b 2 |
1 2 |
Giải thích Với test case thứ nhất, các từ độ dài 3 là: aba,acb,bab,bac,cba. Từ duy nhất kết thúc bằng kí tự 'c' là bac.