Cho một ma trận ~A~ kích thước ~N \times 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.~

Example

Input

4
ABCD
BXZX
CDXB
WCBA

Output

12