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 取模的结果。

无

无

Bessie 可以生成以下回文串： - 1 个 "ABCDCBA" - 1 个 "ABCWCBA" - 6 个 "ABXZXBA" - 4 个 "ABXDXBA"