Palindromic Paths (Bronze)#11169
Farmer John's farm is in the shape of an n \times n grid of fields, with each field labeled by a letter of the alphabet. For example:
Each day, Bessie the cow walks from the upper-left field to the lower-right field. At each step, she moves either one field to the right or one field downward. Bessie keeps track of the string formed by the letters of the fields she visits along her path.
Bessie becomes very disoriented, however, if this string is a palindrome (that is, if it reads the same forward and backward), because she gets confused about the direction in which she was traveling.
Please help Bessie determine the number of distinct palindromes she can form along her walks. Different paths that produce the same palindrome count only once. For example, in the grid above, several different paths produce the palindrome ABXZXBA, but there are only distinct palindromes Bessie can form:
The first line contains an integer n~(2 \le n \le 18). The next lines contain the rows of the grid. Each row consists of characters from to .
Print the number of distinct palindromes Bessie can form.
Example 1