Pig and Palindromes

题意翻译

一只猪走进了一个森林。很凑巧的是，这个森林的形状是长方形的，有$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$ 取余后的结果。 感谢@罗进瑶 提供的翻译

题目描述

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 $ 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.

输出格式

Print a single integer — the number of beautiful paths modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

3 4
aaab
baaa
abba

输出样例 #1

3

说明

Picture illustrating possibilities for the sample test.