← 返回题目列表

AtCoder · abc292_g

G. 计算严格递增序列

中文机器翻译题面 查看原题

分数: 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.