Đường đi Palindrome (Gold)

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

Mỗi đường đi tạo thành một chuỗi $2N-1$ ký tự. Đếm số đường đi tạo thành chuỗi palindrome, lấy modulo ${10}^9+7$.

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

Số đường đi palindrome modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 500$

Ví dụ