分数: 600 点
问题陈述
给你一个序列 S_1,\ldots,S_N 的长度-M 由数字组成的字符串 (0123456789)和 ?.
有 10^q 替换出现的方法 ? 与数字独立,其中 q 是总数 ? in 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.