Score : $500$ points

问题描述

已知 $M$ 个数字 $C_i$。

求在十进制表示下，包含所有 $C_1, \ldots, C_M$ 的整数（不包含前导零）从 $1$ 到 $N$（包含）的和，对 $998244353$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 10:12:30