配点 : $500$ 点

問題文

$M$ 個の数字 $C_i$ が与えられます。

$1$ 以上 $N$ 以下の整数のうち、先頭に余分な $0$ をつけずに $10$ 進法で表した時に $C_1,\ldots,C_M$ を全て含むようなもの全ての和を、 $998244353$ で割った余りを求めてください。

制約

• $1 \leq N < 10^{10^4}$
• $1 \leq M \leq 10$
• $0 \leq C_1 < \ldots < C_M \leq 9$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$M$

$C_1$ $\ldots$ $C_M$

出力

答えを出力せよ。

104
2
0 1

520

$1$ 以上 $104$ 以下の整数のうち、$10$ 進法で表した時に 0, 1 を共に含むようなものは、$10,100,101,102,103,104$ の $6$ 個あります。 これらの和は $520$ です。

999
4
1 2 3 4

0

$1$ 以上 $999$ 以下の整数で、1, 2, 3, 4 を全て含むようなものは存在しません。

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

397365274

$998244353$ で割った余りを求めてください。