/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
104 2 0 1
出力例 1
520
1 以上 104 以下の整数のうち、10 進法で表した時に 0, 1 を共に含むようなものは、10,100,101,102,103,104 の 6 個あります。
これらの和は 520 です。
入力例 2
999 4 1 2 3 4
出力例 2
0
1 以上 999 以下の整数で、1, 2, 3, 4 を全て含むようなものは存在しません。
入力例 3
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 5 0 2 4 6 8
出力例 3
397365274
998244353 で割った余りを求めてください。
Score : 500 points
Problem Statement
Given are M digits C_i.
Find the sum, modulo 998244353, of all integers between 1 and N (inclusive) that contain all of C_1, \ldots, C_M when written in base 10 without unnecessary leading zeros.
Constraints
- 1 \leq N < 10^{10^4}
- 1 \leq M \leq 10
- 0 \leq C_1 < \ldots < C_M \leq 9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M C_1 \ldots C_M
Output
Print the answer.
Sample Input 1
104 2 0 1
Sample Output 1
520
Between 1 and 104, there are six integers that contain both 0 and 1 when written in base 10: 10,100,101,102,103,104.
The sum of them is 520.
Sample Input 2
999 4 1 2 3 4
Sample Output 2
0
Between 1 and 999, no integer contains all of 1, 2, 3, 4.
Sample Input 3
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890 5 0 2 4 6 8
Sample Output 3
397365274
Be sure to find the sum modulo 998244353.