当前没有测试数据。

G - 严格递增的序列的数量

得分：$600$ 点

题目描述

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

有 $10^q$ 种独立替换 ? 为数字的方式，其中 $q$ 是 $S_1,\ldots,S_N$ 中出现的 ? 的总数。在这些替换后的字符串看作整数时，有多少种满足 $S_1\lt S_2 \lt \ldots \lt S_N$ 的替换方案？将答案对 $998244353$ 取模后输出。

替换后的字符串可能有前导零。例如，0000000292 看作 $292$。

限制

• $2 \leq N \leq 40$
• $1 \leq M \leq 40$
• $N$ 和 $M$ 是整数。
• $S_i$ 是一个长度为 $M$ 的字符串，由数字和 ? 组成。

输入

从标准输入中输入数据。

$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

将答案对 $998244353$ 取模后输出。