atcoder#ABC235F. [ABC235F] Variety of Digits

[ABC235F] Variety of Digits

配点 : 500500

問題文

MM 個の数字 CiC_i が与えられます。

11 以上 NN 以下の整数のうち、先頭に余分な 00 をつけずに 1010 進法で表した時に C1,,CMC_1,\ldots,C_M を全て含むようなもの全ての和を、 998244353998244353 で割った余りを求めてください。

制約

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

入力

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

NN

MM

C1C_1 \ldots CMC_M

出力

答えを出力せよ。

104
2
0 1
520

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

999
4
1 2 3 4
0

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

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8
397365274

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