Palindromic Paths

Farmer John's farm is an $N \times N$ grid of fields ($2 \le N \le 18$), and every field carries one uppercase letter from A to Z.

Every day the cow Bessie walks from the field in the upper left corner to the field in the lower right corner. Each step moves her one field to the right or one field down. She reads the letters of the fields she visits, the first and the last one included, so one walk spells a string of length $2N-1$.

Bessie gets disoriented when that string is a palindrome. A palindrome reads the same forward and backward, so she loses track of the direction she walked.

Count the palindromes Bessie can spell. Two walks that spell the same palindrome count once.

Take this grid.

ABCD
BXZX
CDXB
WCBA

Several walks spell ABXZXBA, and Bessie can spell exactly four palindromes: ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

The first line contains $N$. Each of the next $N$ lines contains one row of the grid as $N$ characters in the range A to Z.

Print the number of distinct palindromes Bessie can spell.