AT_abc235_f [ABC235F] Variety of Digits

题目描述

给定 $M$ 个数字 $C_i$。

请你求出所有满足以下条件的 $1$ 到 $N$ 之间的整数（十进制表示且不含前导零）：其十进制表示中包含 $C_1,\ldots,C_M$ 中的所有数字。请输出这些整数的和，结果对 $998244353$ 取模。

输入格式

输入通过标准输入按以下格式给出。

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

输出格式

请输出答案。

样例 1

输入

104
2
0 1

输出

520

样例 2

输入

999
4
1 2 3 4

输出

0

样例 3

输入

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$
• 输入中的所有值均为整数。

样例解释 1

在 $1$ 到 $104$ 之间，十进制表示中同时包含 0 和 1 的数有 $10,100,101,102,103,104$ 共 $6$ 个。它们的和为 $520$。

样例解释 2

在 $1$ 到 $999$ 之间，没有同时包含 1、2、3、4 的数。

样例解释 3

请对 $998244353$ 取模后输出答案。

由 ChatGPT 4.1 翻译