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 thỏa 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 đó xóa đ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 xóa 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ự tùy ý.

Input

• Dòng đầu tiên chứa số nguyên dương ~k~ ~(1 \le k \le 15)~.

• ~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~ ~(1 \le |s| \le 100)~.

Output

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.

Scoring

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

4

Notes

• Ở ví dụ thứ nhất, chữ cái b không thể xuất hiện ở vị trí ~1~ trên từ (~c_{2,1}=0~). Từ điển có ~4~ từ: abc, acb, cab, cba. Trong đó, có ~3~ từ có thể là kết quả giải mã: abc, acb, cab.

• Ở ví dụ thứ hai, chữ cái a không thể xuất hiện ở vị trí ~3~ trên từ (~c_{1,3}=0~); chữ cái c không thể xuất hiện ở vị trí ~1,2~ trên từ (~c_{3,1}=0,c_{3,2}=0~); chữ cái d không thể xuất hiện ở vị trí ~4~ trên từ (~c_{4,4}=0~). Từ điển có ~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.