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$ 取模。

输入格式

从文件 $grace.in$ 中读入数据。

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

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示给定的矩阵 $A$。

输出格式

输出到文件 $grace.out$ 中。

一行一个非负整数表示答案对 $993244853$ 取模后的结果。

样例 1 输入

3 4
noip
ffff
pion

样例 1 输出

2

样例 1 解释

满足条件的两条路径分别为：

1. $(1,1) → (2,1) → (2,2) → (2,3) → (2,4) → (3,4)$；
2. $(1,1) → (1,2) → (2,2) → (2,3) → (3,3) → (3,4)$。

样例 2 输入

4 5
wwwww
wwwww
wwwwa

样例 2 输出

0

样例 3

见右侧文件下的 $grace3.in$ 与 $grace3.ans$。

样例 4

见右侧文件下的 $grace4.in$ 与 $grace4.ans$。

数据范围与提示

对于所有测试数据，保证 $1≤n,m≤500$，保证输入的矩阵仅包含英文小写字母。

每个测试点的具体限制见下表：