Problem
Trang trại của John được biểu thị bằng một lưới các trường N×N (2≤N≤18), mỗi trường được gắn nhãn bằng một chữ cái trong bảng chữ cái. Ví dụ:
ABCD
BXZX
CDXB
WCBA
Hàng ngày, con bò Besi đi từ góc trên bên trái xuống góc dưới bên phải, di chuyển một ô sang phải hoặc một ô xuống dưới. Besi viết ra chuỗi kết quả từ tuyến đường của cô ấy, được xây dựng từ các chữ cái cô ấy đã đi. Cô ấy sẽ rất khó chịu nếu chuỗi kết quả hóa ra là một chuỗi đối xứng (nó đọc giống nhau từ đầu đến cuối và từ đầu đến cuối), vì cô ấy sẽ bối rối không biết mình đã đi theo hướng nào.
Hãy giúp Besie tìm ra bao nhiêu palindrome khác nhau mà cô ấy có thể hình thành trong cuộc hành trình của mình. Các cách khác nhau để tạo thành cùng một bảng màu chỉ nên được tính một lần. Ví dụ: trong ví dụ trên, có một số cách để tạo thành bảng màu nhạt ABXZXBA, nhưng chỉ có 4 bảng màu khác nhau mà Besi có thể tạo thành ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
ĐỊNH DẠNG ĐẦU VÀO :
Dòng đầu tiên chứa N và các dòng tiếp theo N chứa N mô tả trường. Mỗi dòng chứa N ký tự trong phạm vi A..Z.
ĐỊNH DẠNG ĐẦU RA:
In số lượng palindromes riêng biệt mà Besi có thể hình thành.
| Đầu vào |
Đầu ra |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |