Problem4141--USACO 2015 US Open, Bronze Problem 4. Palindromic Paths (Bronze)

4141: USACO 2015 US Open, Bronze Problem 4. Palindromic Paths (Bronze)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Farmer John's farm is in the shape of an N×NN×N grid of fields (2≤N≤182≤N≤18), each labeled with a letter in the alphabet. For example: 
ABCD
BXZX
CDXB
WCBA

Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked.

Please help Bessie determine the number of different palindromes she can form during her walk. Different ways of forming the same palindrome only count once; for example, there are several routes that yield the palindrome ABXZXBA above, but there are only four distinct palindromes Bessie can form, ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.


Input

INPUT FORMAT (file palpath.in):

The first line of input contains NN, and the remaining NN lines contain the NN rows of the grid of fields. Each row contains NN characters that are in the range A..Z.


Output

OUTPUT FORMAT (file palpath.out):

Please output the number of distinct palindromes Bessie can form.


Sample Input Copy 

SAMPLE INPUT:
4
ABCD
BXZX
CDXB
WCBA

Sample Output Copy 

SAMPLE OUTPUT:
4

Source/Category

USACO Bronze 
[Submit] [Status]