$Palindrome$ là tên gọi của những xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi.

Bạn $Ma$ đưa cho bạn $Ka$ một cái bảng vuông có kích thước $n\ast n$ gồm toàn các chữ cái tiếng anh in hoa. Mỗi chữ cái nằm trong một ô của bảng. Ví dụ:

ABCD

BXZX

CAXB

WABA

Với mỗi bước di chuyển được phép sang phải hoặc xuống dưới, $Ma$ nhờ $Ka$ đếm xem có bao nhiêu đường đi từ góc trái trên đến góc dưới phải tạo thành một xâu ký tự là một xâu $Palindrome$. (Chú ý một xâu $Palindrome$ được tạo thành bằng nhiều cách thì chỉ được tính $1$ lần).

Vì bạn $Ka$ học kém nên không thể làm được phải lên laptrinhonline nhờ các bạn làm giúp.

Đầu vào

Dòng đầu gồm một số nguyên dương $n$ là kích thước của bảng vuông $(2\le n\le 18)$.

$n$ dòng tiếp theo mỗi dòng chứa $n$ chữ cái tiếng anh in hoa.

Đầu ra

In ra số xâu $Palindrome$ cần tìm.

Ví dụ

Đầu vào

4
ABCD
BXZX
CAXB
WABA

Đầu ra

2

Giải thích ví dụ

Có 2 đường đi là $ABXAXBA$ và $ABXZXBA$