题目描述

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

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

输入格式

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

$N$ $M$ $C_1$ $\ldots$ $C_M$

输出格式

答えを出力せよ。

题目大意

现在给你 $M$ 个数字 $c_1, c_2,...,c_M$。

求 $N$ 以内有多少个数满足，去掉前导零后，$M$ 个给定数字在剩下的数字中出现。请你输出满足条件的所有数的和。

$n \le 10^{10^4}$，$M \le 10$。

104
2
0 1

520

999
4
1 2 3 4

0

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

397365274

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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