Trang trại của Farmer John có dạng một lưới gồm \(N \times N\) ô đồng (\(2 \le N \le 18\)), mỗi ô được ghi một chữ cái trong bảng chữ cái. Ví dụ:

ABCD
BXZX
CDXB
WCBA

Mỗi ngày, cô bò Bessie đi từ ô trên cùng bên trái đến ô dưới cùng bên phải; ở mỗi bước, cô đi sang ô ngay bên phải hoặc xuống ô ngay bên dưới. Bessie ghi lại chuỗi được tạo nên trong quá trình này từ các chữ cái trên những ô cô đi qua. Tuy nhiên, cô sẽ mất phương hướng nếu chuỗi đó là một palindrome (đọc xuôi và đọc ngược giống nhau), vì cô bối rối không biết mình đã đi theo hướng nào.

Hãy giúp Bessie xác định số palindrome khác nhau mà cô có thể tạo ra trong chuyến đi. Các cách khác nhau tạo ra cùng một palindrome chỉ được tính một lần; chẳng hạn, có nhiều đường đi tạo ra palindrome ABXZXBA trong ví dụ trên, nhưng Bessie chỉ có thể tạo ra bốn palindrome phân biệt: ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), và \(N\) dòng còn lại chứa \(N\) hàng của lưới ô đồng. Mỗi hàng chứa \(N\) ký tự trong khoảng từ A đến Z.

Dữ liệu ra

In số palindrome phân biệt mà Bessie có thể tạo ra.

Ví dụ

4
ABCD
BXZX
CDXB
WCBA

4

Nguồn

USACO 2015 US Open, Bronze — Palindromic Paths (Bronze). Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=548