Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Từ lúc cha sinh mẹ đẻ, Gióng vốn dĩ đã là người nói ít, đã thế lớn lên bố mẹ lại còn băt học ở Viện ngôn ngữ học quốc gia, để nghiên cứu về chuyên ngành “nói” . Rất bất bình về vấn đề này, hiện tại, Gióng đang nghiên cứu ra một loại ngôn ngữ mới để giảm thiểu số từ tạo ra. Trong loại ngôn ngữ này vẫn đưươc biểu diễn bởi 26 chữ cái trong bảng chữ cái alphabet tuy nhiên có thêm nhiều ràng buộc về vị trí giữa các chữ cái. Hãy giúp Gióng đếm xem có tất cả bao nhiêu từ có độ dài L và kết thúc bằng chữ cái C.

Input

-          26 dòng đầu mỗi dòng i gồm 26 số a[i] [j]  ( 0 hoặc 1) cách nhau bởi dấu cách, số thứ j biểu hiện việc chữ cái thứ j có thể đứng liền sau chữ cái thứ i được nếu a[i][j] = 1 và ngược lại khi a[i] [j] = 0 . ( Các chữ cái được đánh số 0 bắt đầu từ ‘a’ và kết thúc tại 25 ở ‘z’).

-          Dòng tiếp theo chứa 1 số nguyên T là số trường hợp kiểm thử (T<=100) .

-          Mỗi dòng trong T dòng tiếp theo gồm một ký tự C ( C là chữ cái in thường) và số nguyên dương L (2<=L <= 10^7).

Output

-          In ra T dòng, mỗi dòng là số lượng từ có độ dài L kết thúc bằng chữ cái C theo ràng buộc ở trên. Kết quả lấy modulo 10^9+7

Example

Input:
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

Output:
1
2