题目描述

徐老师会给定一个 $n * m$ 的小写字母矩阵

从 $(1,1)$ 出发，每次移动可以向右或者向下，直到走到 $(n,m)$ 结束

如果把路径上的所有字母连起来拼成一个字符串，这个字符串是一个回文字符串，则这条路径就是一条回文路径

现在徐老师想知道，在这个矩阵中有多少种不同的移动方案可以构成回文路径。

P.S. 这里统计的是不同的移动方案，而不是不同的回文

输入格式

输入第一行包含两个整数 $n,m$ 含义如题

接下来 $n$ 行，每行包含 $m$ 个小写字母

输出格式

输出一个整数表示方案数，由于答案可能很大，请你把答案对 $993244853$ 取模后输出

数据范围

对于 $20\%$ 的数据满足：$1 \leq n,m \leq 10$

对于 $40\%$ 的数据满足：$1 \leq n,m \leq 20$

对于 $60\%$ 的数据满足：$1 \leq n,m \leq 100$

对于另外 $20\%$ 的数据满足：$min(n,m) \leq 100, max(n,m) \leq 500$

对于 $100\%$ 的数据满足：$1 \leq n,m \leq 500$

样例输入1

3 4
abcd
eeee
dcba

样例输出1

2

样例解释1

两种方案分别为 $abeeba$ 和 $aeeeea$

样例输入2

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

样例输出2

20046