84404 - Palindromic Paths

Farmer John 的农场是一个 N \times N 的网格（1 \le N \le 500），每个格子标有一个字母。例如：

ABCD
BXZX
CDXB
WCBA

每天，奶牛 Bessie 从左上角的格子走到右下角的格子，每一步只能向右或向下移动一个格子。Bessie 会记录下她走过的路径所生成的字符串，这个字符串由她经过的格子上的字母组成。然而，如果这个字符串是一个回文串（即正读和反读相同），她会感到非常困惑，因为她会分不清自己走过的方向。请帮助 Bessie 计算她可以走的不同路径中，对应回文串的数量。即使生成相同回文串的方式不同，也需要分别计数。请输出答案对 1,000,000,007 取模的结果。

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

请输出 Bessie 可以走的不同回文路径的数量，对 1,000,000,007 取模。

Bessie 可以生成以下回文串：

• 1 个 "ABCDCBA"
• 1 个 "ABCWCBA"
• 6 个 "ABXZXBA"
• 4 个 "ABXDXBA"

USACO