nodgd家的花园是一个 \(N\times N\) 的正方形网格，每个格子里都种了一种花，相同的花用同一个大写英文字母表示。

花园有两个门，分别在西北角和东南角。nodgd每次都从西北角的门进入花园，每一步都向东或者向南行走，直到从东南角的门离开花园。

nodgd很喜欢回文，所以nodgd想让你帮忙统计一下，有多少条路径是回文的？答案可能很大， \(\bmod 10^9+7\) 。

第一行一个整数 \(N\) 。

接下来是一个 \(N\times N\) 的字符矩阵，只包含大写英文字母。

输出一个整数，表示回文路径的数量。

样例说明

有以下一些回文路径：

• ABCDCBA 有 $1$ 条
• ABCWCBA 有 $1$ 条
• ABXZXBA 有 $6$ 条
• ABXDXBA 有 $4$ 条

数据范围

对于10%的数据， \(N\leq 8\) ；

对于45%的数据， \(N\leq 18\) ；

对于60%的数据， \(N\leq 150\) ；

对于100%的数据， $1\leq N\leq 500$ 。