CF570E.Pig and Palindromes

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.

小猪佩奇正在散步，一不小心走进了森林。多么奇妙的巧合啊！这座森林呈矩形，由 $n$ 行 $m$ 列组成。我们从上到下依次用数字 $1$ 到 $n$ 给各行编号，从左到右依次用数字 $1$ 到 $m$ 给各列编号。记第 $r$ 行与第 $c$ 列交叉处的格子为 $(r,\,c)$。

初始时，小猪位于格子 $(1,\,1)$，而她最终希望到达格子 $(n,\,m)$。由于小猪急着回家，她只能从格子 $(r,\,c)$ 移动到格子 $(r+1,\,c)$ 或 $(r,\,c+1)$，且不能走出森林边界。

佩奇所在的这片森林非常特别：某些格子彼此相似，而另一些则看起来截然不同。佩奇喜欢拍照，每走一步，她都会为自己当前所在的格子拍一张照片。若她在穿越森林过程中所拍摄的照片，无论按前进顺序还是按逆序观看，都呈现完全相同的图像序列，则称这条路径是“优美的”。更准确地说，按访问顺序排列的格子序列必须构成一个回文（关于回文的正式定义，请参见上一题）。

请计算从格子 $(1,\,1)$ 到格子 $(n,\,m)$ 的优美路径总数。由于该数目可能极大，请输出其对 $10^9 + 7$ 取模的结果。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$）——表示场地的高度和宽度。

接下来的 $n$ 行，每行包含 $m$ 个小写英文字母，用于标识森林中各类单元格。相同类型的单元格用相同的字母表示，不同类型的单元格用不同的字母表示。

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

输出一个整数——美丽路径的数量对 $10^9 + 7$ 取模的结果。

Picture illustrating possibilities for the sample test.

展示样例测试的可能情况。