Trong học kỳ quân đội, mỗi học viên được đòi hỏi phải có kỹ năng sống sót trong mọi tình huống, bên cạnh đó phải hiểu được các ám hiệu chỉ dẫn do chỉ huy đưa ra.

Bài tập huấn luyện như sau: mỗi học viên bị nhốt trong một mê cung hình vuông, mê cung chia thành NxN (1 <= N <= 500) căn phòng, mỗi căn phòng được đại diện bởi một chữ cái trong khoảng từ A đến Z (các chữ cái có thể trùng nhau giữa các phòng). Mê cung được thiết kế sao cho học viên, trong mỗi bước đi, chỉ có thể đi xuống hoặc đi sang phải và không được quay đầu lại. Lối vào mê cung nằm ở căn phòng ngoài cùng phía trên, bên trái và lối thoát là căn phòng ngoài cùng phía dưới, bên phải.

Chỉ dẫn duy nhất được cung cấp: đường đi có các kí tự ghép lại thành chuỗi đối xứng (chuỗi palindrome) sẽ là lối thoát.

Một chuỗi được gọi là Palindrome khi nó đều giống nhau nếu đọc xuôi hay đọc ngược.
Ví dụ:
- Những chuỗi sau là palindrome: "racecar", "abba", "x"
- Những chuỗi sau không là palindrome: "abc", "racecars", "xy".

Cho sẵn mê cung, hãy xem có tất cả bao nhiêu lối thoát (các chuỗi đối xứng có thể giống nhau).

Dữ liệu đầu vào:
- Dòng đầu tiên chứa số nguyên N.
- N dòng tiếp theo, mỗi dòng chứa N ký tự mô tả mê cung (giữa các ký tự không có khoảng trắng).

Dữ liệu đầu ra:
- Ghi lại kết quả là số lối thoát có thể có chia dư cho 1,000,000,007