Đường đi Palindrome (Bronze)

Cho một lưới $N\times N$ ($2\le N\le 18$), mỗi ô chứa một chữ cái in hoa từ A–Z. Bessie xuất phát từ góc trên-trái và đi đến góc dưới-phải, chỉ được di chuyển sang phải hoặc xuống dưới mỗi bước.

Mỗi đường đi tạo thành một chuỗi $2N-1$ ký tự (nối các ký tự trên đường đi). Hỏi có bao nhiêu chuỗi palindrome phân biệt mà Bessie có thể tạo ra?

Dữ liệu vào

• Dòng đầu: số nguyên $N$
• $N$ dòng tiếp theo: mỗi dòng $N$ ký tự in hoa mô tả lưới

Dữ liệu ra

Một số nguyên — số lượng chuỗi palindrome phân biệt.

Ràng buộc

• $2\le N\le 18$

Ví dụ