You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

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

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

【输入格式】

从文件 palin.in 中读入数据。

第一行是两个正整数 n, m。

接下来 n 行，每行是一个长为 m 的字符串，其中只包含英文小写字母，描述矩阵 A 的内容。

【输出格式】

输出到 palin.out 中。

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

【输入样例 1】

见选手目录下的 palin/palin1.in。

3 4
noip
ffff
pion

【输出样例 1】

见选手目录下的 palin/palin1.ans。

2

【样例解释 1】

满足条件的路径为 (1, 1) → (2, 1) → (2, 2) → (2, 3) → (2, 4) → (3, 4) 和 (1, 1) → (1, 2) →

(2, 2) → (2, 3) → (3, 3) → (3, 4)。

【输入样例 2】

见选手目录下的 palin/palin2.in。

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

【输出样例 2】

见选手目录下的 palin/palin2.ans。

20046

【数据规模与约定】

对于 20% 的数据，1 ≤ n, m ≤ 10。

对于 35% 的数据，1 ≤ n, m ≤ 20。

对于 50% 的数据，1 ≤ n, m ≤ 80。

对于另外 15% 的数据，1 ≤ n ≤ 80。

对于另外 15% 的数据，保证对任意 i > 1, j < m 有 Ai,j = Ai−1,j+1。

对于 100% 的数据，1 ≤ n, m ≤ 500，输入的矩阵仅包含小写英文字母。