题解：
首先观察到题目要求的是合法回文串的个数，而回文串要求从前往后和从后往前是一样的，因此我们假设有两只猪，分别从左上和右下开始走，走相同的步数最后相遇，那么它们走的路能拼在一起构成一个回文串，当且仅当它们走字符串是完全相同的。
那么我们可以根据这个性质进行DP，设f[i][j][k][l]表示第一只猪走到(i, j),第二只猪走到(k, l)的方案数。
那么观察到$i + j = k + l$,所以$l$是没必要记录的，因为前面三个确定，l就确定了，然后因为i从1 开始枚举，每次只能走一步，所以只会用到上一步的方案，所以可以滚动一下，这样时空复杂度就都可以承受了。
因为要限制两只猪走的步数一样，注意限制第一只猪在红色的三角形中，另一只猪在蓝色的三角形中。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 510
#define mod 1000000007
#define LL long long int n, m;
LL f[][AC][AC], ans;
char s[AC][AC]; void pre()
{
scanf("%d%d", &n, &m);
for(R i = ; i <= n; i ++) scanf("%s", s[i] + );
if(s[][] != s[n][m]) {printf("0\n"); exit();}
} inline bool check(int i, int j, int k, int l)
{
if(i == k && j == l) return true;
else if(i + == k && j == l) return true;
else if(i == k && j + == l) return true;
return false;
} void work()
{
int l, now = , b = (n + m) / ;
f[][][n] = ;
for(R i = ; i <= n; i ++, now ^= )
{
for(R j = ; j + i - <= b; j ++)
{
if(i == && j == ) continue;
for(R k = n; k >= i; k --)
{
l = n + m + - i - j - k;
if(l < j || l > m) continue;
if(s[i][j] != s[k][l]) continue;
f[now][j][k] = f[now ^ ][j][k] + f[now ^ ][j][k + ];
f[now][j][k] += f[now][j - ][k] + f[now][j - ][k + ];
f[now][j][k] %= mod;
if(check(i, j, k, l)) ans += f[now][j][k];
if(ans > mod) ans -= mod;
}
}
memset(f[now ^ ], , sizeof(f[now ^ ]));//因为有同层转移，所以要memset，而不能枚举到它的时候再重置
}
printf("%lld\n", ans);
} void work1()
{
int l, now = , b = (n + m) / ;
f[][][n] = ;
for(R i = ; i <= n; i ++, now ^= )
{
for(R j = ; j + i - <= b; j ++)
{
if(i == && j == ) continue;
for(R k = n; k >= i; k --)
{
l = n + m + - i - j - k;
if(l < j || l > m) continue;
if(s[i][j] != s[k][l]) continue;
f[i][j][k] += f[i - ][j][k] + f[i - ][j][k + ];
f[i][j][k] += f[i][j - ][k] + f[i][j - ][k + ];
f[i][j][k] %= mod;
if(check(i, j, k, l)) ans += f[i][j][k];
if(ans > mod) ans -= mod;
}
}
}
printf("%lld\n", ans);
} int main()
{
// freopen("in.in", "r", stdin);
pre();
work();
// fclose(stdin);
return ;
}