Bình rất đam mê khảo cổ học. Anh vừa phát hiện một từ điển cổ, sau khi nghiên cứu Bình đã tìm ra một vài quy tắc của nó như sau:

• Từ điển chỉ sử dụng \(k\) loại ký tự, có thể được Bình biểu diễn bằng \(k\) chữ cái đầu tiên trong bảng chữ cái Latin in thường.
• Mỗi từ trong từ điển đều có độ dài bằng đúng \(k\) và chứa các chữ cái khác nhau. Nói cách khác, mỗi từ đều là một hoán vị của \(k\) chữ cái.
• Mỗi chữ cái chỉ có thể đứng ở một số vị trí nhất định trên từ. Bình biểu diễn quy tắc này bằng một ma trận \(c\) kích thước \(k \times k\). Giá trị của \(c_{i,j}\) bằng 1 hoặc 0 tương ứng là ký tự thứ \(i\) trong bảng chữ cái được phép xuất hiện ở vị trí \(j\) trên từ hoặc không.

Từ nào thoả mãn cả ba quy tắc trên thì đều có trong từ điển.

Bình sẽ sử dụng từ điển này để giải mã một thông điệp mà anh vừa tìm được. Thông điệp đã lâu đời nên có thể có một số vị trí bị mờ. Bình biểu diễn thông điệp bằng một xâu \(s\) chỉ chứa các ký tự Latin in thường và dấu * (dấu * đại diện cho các vị trí bị mờ). Để giải mã thông điệp, anh đã thử thay mỗi dấu * bằng một ký tự (các dấu * không nhất thiết được thay bằng các ký tự giống nhau), sau đó xoá đi một số ký tự trên \(s\) và giữ nguyên thứ tự các ký tự còn lại (có thể không xoá ký tự nào). Nếu xâu thu được là một từ trong từ điển thì Bình đã thu được một kết quả giải mã.

Yêu cầu

Hãy tính xem Bình có thể thu được bao nhiêu kết quả giải mã khác nhau. Tức là đếm xem trong từ điển có bao nhiêu từ là xâu con (không cần liên tiếp) của \(s\), với dấu * đại diện cho ký tự tuỳ ý.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(k\).
• \(k\) dòng tiếp theo, mỗi dòng chứa \(k\) số nguyên. Ở trên dòng thứ \(i\), số thứ \(j\) là \(c_{i,j}\).
• Dòng tiếp theo chứa xâu \(s\).

Dữ liệu ra

• Ghi một số nguyên duy nhất là số kết quả giải mã khác nhau mà Bình có thể thu được.

Input 1

3
1 1 1
0 1 1
1 1 1
ad*a*

Output 1

3

Giải thích

• Từ điển có 4 từ: abc, acb, cab, cba. Trong đó 3 từ có thể là kết quả giải mã: abc, acb, cab.

Input 2

4
1 1 0 1
1 1 1 1
0 0 1 1
1 1 1 0
cdefab*f*

Output 2

4

Giải thích

• Các từ thoả mãn từ điển là 8 từ: abdc, adbc, adcb, badc, bdca, dabc, dacb, dbca. Trong đó, có 4 từ có thể là kết quả giải mã: abdc, dabc, dacb, dbca.

Ràng buộc

• Trong tất cả các test: \(1 \le k \le 15\); độ dài xâu \(s\) không quá \(100\).
• Có 30% số test với \(k \le 10\).
• Có 30% số test với xâu \(s\) chỉ gồm các ký tự dấu sao *.
• Có 40% số test với ràng buộc gốc.