P3126 [USACO15OPEN] Palindromic Paths G

题目描述

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 取模。

输入输出样例 1

4
ABCD
BXZX
CDXB
WCBA

12

说明/提示

Bessie 可以生成以下回文串：

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