题目描述

农民约翰的农场呈$\red{N×}$$\red{N}$网格状$\red{（2≤}$$\red{N≤}$$\red{18）}$ ，每个都用字母表中的一个字母标记。例如：

ABCD
BXZX
CDXB
WCBA

每天，奶牛贝西从左上角的田地走到右下角的田地，每走一步，她要么向右走，要么向下走。贝西跟踪她在这个过程中生成的字符串，这些字符串是由她走过的字母组成的。然而，如果这条线是回文（向前读和向后 读一样），她会非常迷失方向，因为她对自己走的方向感到困惑。

请帮助贝西确定她走路时可以形成的不同回文的数量。形成同一回文的不同方式只计算一次；例如，有几种途径产生上述回文$\red{ABXZXBA，}$但贝西只能形成四种不同的回文，$\red{ABCDCBA}$、$\red{ABCWCBA}$、$\red{ABXZXBA}$、$\red{ABXDXBA}$。

输入格式

第一行输入包含$\red{N}$行，其余$\red{N}$行包含字段网格的$\red{N}$行。每行包含$\red{N}$个字符，范围为$\red{A...Z}$

输出格式

请输出贝西可以形成的不同回文数。

样例

输入样例

4
ABCD
BXZX
CDXB
WCBA

输出样例

4