题目描述

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

有 $10^q$ 种独立地用数字替换 ? 的方式，其中 $q$ 是 $S_1, \\ldots, S_N$ 中 ? 的总数。在这些替换后的字符串被看作整数时，有多少种满足 $S_1 < S_2 < \\ldots < 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$

输出

打印答案。

示例输入 1

3 2
?0
??
05

示例输出 1

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

2 1
0
0

示例输出 2

0

示例输入 3

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??

示例输出 3

137811792

对 $998244353$ 取模后的计数。