Score : $600$ points

问题陈述

你将获得一个长度为 $M$ 的字符串序列 $S_1,\ldots,S_N$，由数字字符（0123456789）和 ? 组成。

其中共有 $q$ 个 ?，存在 $10^q$ 种独立替换 ? 为数字的方式。在所有这些方式中，有多少种使得替换后的字符串作为整数时满足 $S_1\lt S_2 \lt \ldots \lt S_N$？请找出这个计数结果对 $998244353$ 取模的值。

需要注意的是，替换后的字符串可能包含前导零。例如，0000000292 被视为整数 $292$。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 12:11:27