Dưới đây là bài toán được đề cập đến trong tiêu đề, nếu ai có lời giải thì hãy comment bằng cú pháp:

<tên>
dùng dấu "```" ở hai đầu để viết được code vào đó:
VD:
Nguyen Van A:
"```"
code
"```"

*Lưu ý: Dấu ``` để riêng ra ngoài và không cho vào ngoặc hay để trên 1 dòng, phải làm đúng như trên thì code mới hiện thị chuẩn format khi gõ được

Dưới đây là đề bài:

ĐẾM ĐƯỜNG ĐI ĐỐI XỨNG:

Cho một ma trận A kích thước N x N (1 ≤ N ≤ 500) Các hàng đánh số từ 1 đến N từ trên xuống dưới, các cột đánh số từ 1 đến N từ trái qua phải. Ô nằm trên hàng i, cột j gọi là ô A[i][j] có giá trị là các chữ cái latin in hoa. Xét các đường đi từ ô (1; 1) đến ô (N; N) mà trong một bước đi bạn chỉ được phép di chuyển xuống dưới hoặc qua phải. Mỗi đường đi được đại diện bởi một xâu được tạo thành bằng cách viết liên tiếp các kí tự trên đường đi. Hãy đếm số lượng đường đi có xâu đại diện là xâu đối xứng.

Input:

Dòng đầu tiên là số nguyên N là kích thước của ma trận.
N dòng tiếp theo mỗi dòng gồm một xâu đại diện cho hàng thứ i của ma trận.

Output:

Gồm một dòng duy nhất là số lượng đường đi có xâu đại diện là xâu đối xứng sau khi chia lấy dư cho (10^9) + 7

Sample Input:

4
ABCD
BXZX
CDXB
WCBA

Sample Output:

12