回文路径

成绩 100 开启时间 2019年09月16日 星期一 23:15
折扣 0.8 折扣时间 2019年09月16日 星期一 23:15
允许迟交 是 关闭时间 2019年09月16日 星期一 23:15

【题目描述】回文路径（path）USACO 2015

农夫FJ的农场是一个N×N的正方形矩阵（2≤N≤500），每一块用一个字母作标记。比如说：

ABCD

BXZX

CDXB

WCBA

某一天，FJ从农场的左上角走到右下角，当然啦，每次他只能往右或者往下走一格。FJ把他走过的路径记录下来。现在，请你帮他统计一下，所有路径中，回文串的数量（从前往后读和从后往前读一模一样的字符串称为回文串）。

【输入格式】

第一行包括一个整数N，表示农场的大小，接下来输入一个N×N的字母矩阵。

【输出格式】

　　输出一个整数，表示回文串的数量，因为数值可能非常大，所以要对此数取1 000 000 007的模。

【输入样例】

　　4

ABCD

BXZX

CDXB

WCBA

【输出样例】

12

【样例说明】

1×"ABCDCBA"

1×"ABCWCBA"

6×"ABXZXBA"

4×"ABXDXBA"