U323753 回文路径

Farmer John 的农场是一片 N × N 网格形状的区域（ 2 ≤ N ≤ 18 ），每个格子用一个字母表中的字母进行标 记。例如： ``` ABCD BXZX CDXB WCBA ``` 每一天，奶牛 Bessie 从左上角的格子走到右下角的格子，每一步她可以走到右边或者下边的格子。 Bessie 记录下 了这个过程中由她走过的字母所形成的字符串，然而，当这个字符串是一个回文串（顺着读和逆着读一样）的时候，她就会迷失方向，因为她会搞不清她走过的是哪个方向。 请帮助 Bessie 计算她可能走出多少种不同的回文串。**不同的路径形成的相同字符串只计算一次**；例如，上例中有多条不同的路径会产生回文 ABXZXBA ，但 Bessie 只能够得到四种不同的回文， ABCDCBA、 ABCWCBA、ABXZXBA、ABXDXBA 。

输入的第一行包含 N ，接下来 N 行描述网格区域的 N 行，每行包含 N 个字符，都在范围 A..Z 内。

请输出 Bessie 可以得到的不同的回文数量。