严格递增序列计数

题目描述

给定由数字(0123456789)和 ? 组成、长度为 $M$ 的字符串序列 $S_1,\ldots,S_N$。

将所有的 ? 独立地替换为数字,共有 $10^q$ 种替换方式,其中 $q$ 是 $S_1,\ldots,S_N$ 中 ? 的总个数。在这些替换方式中,将替换后得到的字符串分别视为整数时,满足

[ S_1 \lt S_2 \lt \ldots \lt S_N ]

的替换方式有多少种?请计算该数量对 $998244353$ 取模的结果。

另外,替换后的 $S_i$ 开头可以连续出现一个或多个 0。例如,0000000292 视为整数 $292$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$S_1$
$\vdots$
$S_N$

输出格式

输出答案。

样例

3 2
?0
??
05

4

满足条件的四种替换方式如下。

将 $S_1$ 的第一个字符替换为 0,将 $S_2$ 的第一个和第二个字符分别替换为 0 和 1。

将 $S_1$ 的第一个字符替换为 0,将 $S_2$ 的第一个和第二个字符分别替换为 0 和 2。

将 $S_1$ 的第一个字符替换为 0,将 $S_2$ 的第一个和第二个字符分别替换为 0 和 3。

将 $S_1$ 的第一个字符替换为 0,将 $S_2$ 的第一个和第二个字符分别替换为 0 和 4。

2 1
0
0

0

10 10
1?22??37?4
1??8?0??49
3?02??8044
51?4?8?7??
5?9?20???2
68?7?6?800
?3??2???23
?442312158
??2??921?8
????5?96??

137811792

数据范围

• $2 \le N \le 40$
• $1 \le M \le 40$
• $N,M$ 是整数
• $S_i$ 是由数字和 ? 组成、长度为 $M$ 的字符串