John's farm is represented by a lattice of N×N fields (1≤N≤500). Each field is represented by a Latin alphabet character. For example:
ABCD
BXZX
CDXB
WCBA
Every day Besi the cow walks from the top left corner to the bottom right corner, each time moving one step to the right or down. Besi writes down the letters that she walked over in a line. She will be upset if she gets a palindrome (a word that reads the same from left to right and right to left), because then she will get confused in which direction she was moving.
Please help Besie determine the number of different paths she can take to get palindromes. Different ways in which the same palindromes are obtained count many times. Print your answer modulo 1,000,000,007.
INPUT FORMAT:
The first line of the input contains N, and the next N lines contain N lines of the grid describing the fields. Each line contains N characters in the interval A..Z.
OUTPUT FORMAT:
Print the number of different Besi paths that form palindromes modulo 1,000,000,007.
|
Enter |
Output |
|
4
ABCD
BXZX
CDXB
WCBA
|
12 |
Note:
Besi can make the following palindromes:
1 x "ABCDCBA"
1 x "ABCWCBA"
6 x "ABXZXBA"
4 x "ABXDXBA"