题目描述

农民约翰的农场呈$\red{N×}$$\red{N}$的农田网格状$\red{（1≤}$$\red{N≤}$$\red{500）}$，每个标签上都有字母表中的一个字母。例如：

ABCD
BXZX
CDXB
WCBA

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

请帮助贝西确定对应回文的不同路径的数量。多次获得相同回文数的不同方法。请打印您的答案，模数$\red{100000007}$。

输入格式

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

输出格式

请输出贝西可以采用的不同回文路径数，模$\red{100000007}$。

样例

输入样例

4
ABCD
BXZX
CDXB
WCBA

输出样例

12

提示

贝西可以制作以下回文

$\red{1 x }$"$\red{ABCDCBA}$"

$\red{1 }$个"$\red{ABCWCBA}$"

$\red{6 x}$"$\red{ABXZXBA}$"

$\red{4 x}$"$\red{ABXDXBA}$"