题目描述

给定一个$\red{n}$行$\red{m}$列的只包含小写字母的矩阵$\red{A，}$请求出从$\red{(1,1)}$到$\red{(n,m)}$只向下或向右走，且路径上 的所有字符按照顺序排列可以构成一个回文串的路径条数。

由于答案可能很大，请输出答案在模$\red{993244853}$意义下的结果。

输入格式

第一行输入两个正整数 $\red{n, m}$。$\red{(1<=n,m<=500)}$

之后 $\red{n }$行，每行输入一个长为 $\red{m }$的字符串，其中只包含英文小写字母，描述矩阵 $\red{A }$的内容。

输出格式

输出一行一个非负整数，表示满足条件的路径数模$\red{993244853}$后的值。

样例

输入样例1

3 4
noip
ffff
pion

输出样例1

2

输入样例2

4 5
wwwww
wwwww
wwwww
wwwwa

输出样例2

0

输入样例3

10 12
abbcbdbababa
bcccdcdccccb
bcccccccccca
ccccdcdcdcdb
bdcdcccccccd
dcccccccdcdb
bdcdcdcdcccc
accccccccccb
bccccdcdcccb
abababdbcbba

输出样例3

20046

提示

样例$\red{1：}$满足条件的路径为 $\red{(1,1) →}$$\red{(2,1) →}$$\red{(2,2) →}$$\red{(2,3) →}$$\red{(2,4) →}$$\red{(3,4) }$和 $\red{(1,1) →}$$\red{(1,2) →}$ $\red{(2,2) →}$$\red{(2,3)}$ $\red{→}$$\red{(3,3) →}$$\red{(3,4)}$。

样例$\red{2：}$由于左上角和右下角的字符不同，任何路径上的字符都不可能构成回文串。