Problem
John's farm is represented by a grid of N×N fields (2≤N≤18), each labeled with a letter of the alphabet. For example,
ABCD
BXZX
CDXB
WCBA
Every day Besi the cow goes from the upper left corner to the lower right, moving either one cell to the right or one cell down. Besi writes down the string that results from her route, built from the letters she walked. She will be very upset if the resulting string turns out to be a palindrome (it reads the same from beginning to end and from end to beginning), because she will get confused in which direction she went.
Please help Besie figure out how many different palindromes she can form during her journey. Different ways to form the same palindrome should only be counted once. For example, in the example above, there are several ways to form the palindrome ABXZXBA, but there are only 4 different palindromes that Besi can form ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
INPUT FORMAT :
The first line of input contains N and subsequent N lines contain N< /strong> field description. Each line contains N characters in the range A..Z.
OUTPUT FORMAT :
Print the number of distinct palindromes Besi can form.
| Input |
Output |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |