本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

农夫约翰的农场呈一个 $N \times N$ 的方格田地（$2 \le N \le 18$），每个格子都标有一个字母。例如： ABCD BXZX CDXB WCBA

每天，奶牛贝茜从左上角的格子走到右下角的格子，每一步要么向右走一格，要么向下走一格。贝茜会记录她在行走过程中经过的字母所生成的字符串。若这个字符串是一个回文串（正读与反读相同），她就会非常迷惑，因为她会搞不清自己是朝哪个方向走的。

请帮助贝茜确定：在她的行走过程中，她能够形成多少种不同的回文串。形成同一个回文串的不同走法只计一次；例如，上面有多条路径会得到回文串 ABXZXBA，但贝茜一共只能形成四种不同的回文串：ABCDCBA、ABCWCBA、ABXZXBA、ABXDXBA。

输入格式

第一行输入为 $N$，接下来的 $N$ 行包含网格的 $N$ 行。每行包含 $N$ 个字符，字符范围为 A..Z。

输出格式

请输出贝茜能够形成的不同回文串的数量。

4
ABCD
BXZX
CDXB
WCBA

4

提示

[题目来源：Brian Dean，2015]

来源

USACO|2015|Bronze