该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

强哥 的农场是一片 $N \times N$ 网格形状的区域（ $2 ≤ N ≤ 18$ ），每个格子用一个字母表中的字母进行标记。例如：

ABCD
BXZX
CDXB
WCBA

每一天，Petr强 从左上角的格子走到右下角的格子，每一步她可以走到右边或者下边的格子。 Petr强 记录下了这个过程中由她走过的字母所形成的字符串，然而，当这个字符串是一个回文串（顺着读和逆着读一样）的时候，她就会迷失方向，因为她会搞不清她走过的是哪个方向。

请帮助 Petr强 计算她可能走出多少种不同的回文串。不同的路径形成的相同字符串只计算一次；例如，上例中有多条不同的路径会产生回文 ABXZXBA ，但 Petr强 只能够得到四种不同的回文， ABCDCBA 、 ABCWCBA 、 ABXZXBA 、 ABXDXBA 。

输入格式

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

输出格式

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

4
ABCD
BXZX
CDXB
WCBA

4

提示