题目描述

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

输入格式

第一行两个整数 $n,m$，$1\le n,m\le 500$。

接下来是一个 $n$ 行 $m$ 列的矩阵，由小写字母组成。

输出格式

一个整数表示答案，对 $10^9+7$ 取余。

3 4
aaab
baaa
abba

3