Cho một xâu S gồm các ký tự Latin và dấu  * . Mỗi dấu  *  trong xâu có thể được thay thế bằng một ký tự Latin bất kỳ.

Bạn được yêu cầu đếm số lượng hoán vị của K kí tự đầu tiên (ví dụ K = 3, ta có hoán vị là "abc", "acb", "bac", "bca", "cab", "cba") thỏa mãn tính chất sau:

Cho một ma trận kích thước K × K, trong đó phần tử tại hàng i, cột j biểu thị rằng ký tự Latin thứ i có thể xuất hiện ở vị trí thứ j trong xâu hoán vị (C[2][3] = 1, thì kí tự "b" có thể đặt vào vị trí số 3, ngược lại C[2][3] = 0 thì những xâu như "acb" sẽ không được tính do có kí tự b ở vị trí 3).

Yêu cầu: Đếm số các hoán vị thoả mãn và được đếm là một xâu con không cần liên tiếp của S (ví dụ "abc" và "acb" đều là xâu con của "a**b", trong khi "bac" thì không phải xâu con của S).

Input

Dòng đầu tiên là số nguyên dương K (1 ≤ K ≤ 15)

Mỗi dòng trong K dòng tiếp theo, gồm K số nguyên C[i][j] là 0 hoặc 1

Dòng tiếp theo là một xâu S (1 ≤ |S| ≤ 100)

Output

In ra đáp án của bài toán.

Ràng buộc

• Subtask $1$ ($30\%$): $1 < K < 10$
• Subtask $2$ ($30\%$): S chỉ chứ kí tự *
• Subtask $3$ ($40\%$): không có ràng buộc gì

KSTRING.INP

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

STRING.OUT

3

KSTRING.INP

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

KSTRING.OUT

4