码农谷 > 问答 > 编程题 > Pig and Palindromes

Pig and Palindromes

提问者: 老码农     发布时间:2017-01-11     浏览:4     回复:0     悬赏:0.0 谷币

Peppa the Pig was walking and walked into the forest. What a strange coincidence! The forest has the shape of a rectangle, consisting of n rows and m columns. We enumerate the rows of the rectangle from top to bottom with numbers from 1 to n, and the columns — from left to right with numbers from 1 to m. Let's denote the cell at the intersection of the r-th row and the c-th column as (r, c).

Initially the pig stands in cell (1, 1), and in the end she wants to be in cell (n, m). Since the pig is in a hurry to get home, she can go from cell (r, c), only to either cell (r + 1, c) or (r, c + 1). She cannot leave the forest.

The forest, where the pig is, is very unusual. Some cells of the forest similar to each other, and some look very different. Peppa enjoys taking pictures and at every step she takes a picture of the cell where she is now. The path through the forest is considered to be beautiful if photographs taken on her way, can be viewed in both forward and in reverse order, showing the same sequence of photos. More formally, the line formed by the cells in order of visiting should be a palindrome (you can read a formal definition of a palindrome in the previous problem).

Count the number of beautiful paths from cell (1, 1) to cell (n, m). Since this number can be very large, determine the remainder after dividing it by 109 + 7.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the height and width of the field.

Each of the following n lines contains m lowercase English letters identifying the types of cells of the forest. Identical cells are represented by identical letters, different cells are represented by different letters.

Output

Print a single integer — the number of beautiful paths modulo 109 + 7.


输入样例:
3 4
aaab
baaa
abba

输出样例:
3

我要挑战
其他解答 共0条
 
温馨提示:本问答中心的任何言论仅代表发言者个人的观点,与码农谷立场无关。请对您的言论负责,遵守中华人民共和国有关法律、法规。如果您的言论违反码农谷问答中心的规则,将会被删除。
验证码: 看不清?点击图片更换    

关注码农谷微信
专家推荐
老码农     向TA提问 最佳答案:67
冰点     向TA提问 最佳答案:28
itner     向TA提问 最佳答案:11
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1