题目描述

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

ABCD
BXZX
CDXB
WCBA

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

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

输入格式

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

输出格式

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

样例

输入样例

4
ABCD
BXZX
CDXB
WCBA

输出样例

4