农夫约翰的农场可视为一个 N×N 的方格矩阵,每个方格区域内都标有字母,例如:
ABCD BXZX CDXB WCBA
每天,奶牛贝茜会从左上角土地出发走向右下角土地。
每次移动,她可以向下或向右移动一个格子。
贝茜会记录行动过程中生成的字符串,这些字符串是由她走过的方格所标记字母构成的。
如果构成的字符串是回文的(从前往后读与从后往前读一样),她就会对自己的行进方向感到疑惑。
请帮助贝茜确定,共有多少种不同的行进路径构成的字符串是回文串。
如果多条不同的路径所构成的回文串相同,则应多次计数。
输出对 109+7 取模后的结果。
第一行包含整数 N。
接下来 N 行,每行包含 N 个大写字母(范围 A∼Z),表示方格矩阵。
输出所有构成回文串的路径数量对 109+7取模后的结果。
1≤N≤500
4 ABCD BXZX CDXB WCBA
12
贝茜的行走路径构成的回文串如下:
ABCD BXZX CDXB WCBA
Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked.
Please help Bessie determine the number of distinct routes she can take that correspond to palindromes. Different ways of obtaining the same palindrome count multiple times. Please print your answer modulo 1,000,000,007.
4 ABCD BXZX CDXB WCBA
12
Bessie can make the following palindromes
[Problem credits: Brian Dean, 2015]