102926: [Atcoder]ABC292 G - Count Strictly Increasing Sequences

Problem Statement

You are given a sequence $S_1,\ldots,S_N$ of length-$M$ strings consisting of digits (0123456789) and ?.

There are $10^q$ ways to replace the occurrences of ? with digits independently, where $q$ is the total number of ? in $S_1,\ldots,S_N$. Among them, how many satisfy $S_1\lt S_2 \lt \ldots \lt S_N$ when the resulting strings are seen as integers? Find this count modulo $998244353$.

The resulting strings may have leading zeros. For instance, 0000000292 is seen as $292$.

Constraints

• $2 \leq N \leq 40$
• $1 \leq M \leq 40$
• $N$ and $M$ are integers.
• $S_i$ is a string of length $M$ consisting of digits and ?.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 2
?0
??
05

Sample Output 1

4

Here are the four desired replacements.

• Replace the first character of $S_1$ with 0, and the first and second characters of $S_2$ with 0 and 1, respectively.
• Replace the first character of $S_1$ with 0, and the first and second characters of $S_2$ with 0 and 2, respectively.
• Replace the first character of $S_1$ with 0, and the first and second characters of $S_2$ with 0 and 3, respectively.
• Replace the first character of $S_1$ with 0, and the first and second characters of $S_2$ with 0 and 4, respectively.

Sample Input 2

2 1
0
0

Sample Output 2

0

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

Sample Output 3

137811792

Find the count modulo $998244353$.

问题描述

给你一个由数字（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$的结果。

得到的字符串可能有前导零。例如，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$的结果。