\(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 * 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\)