G - Collect Them All Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

箱の中に N 枚のカードが入っています。各カードには 1 以上 M 以下の整数が 1 つ書かれており、各 i=1,\ldots,M について、i が書かれたカードは C_i 枚あります。

あなたは何も書かれていないノートを持った状態から、次の操作を繰り返します。

  • 箱の中からランダムにカードを 1 枚取り出す。取り出したカードに書かれている整数をノートに書き、カードを箱の中に戻す。

ノートに 1 以上 M 以下の整数が全て 1 個以上書かれている状態になるまでの操作回数の期待値を \bmod 998244353 で求めてください。

期待値 {}\bmod{998244353} の定義 この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac yx で表したときに x が 998244353 で割り切れないことが保証されます。 このとき、y\equiv xz\pmod{998244353} を満たす 0\leq z\lt998244353 がただ一つ存在するので、z を出力してください。

制約

  • 1 \leq M \leq N \leq 2\times 10^5
  • 1 \leq C_i
  • \sum_{i=1}^{M}C_i=N
  • 入力は全て整数である

入力

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

N M
C_1 \ldots C_M

出力

答えを出力せよ。

入力例 1

2 2
1 1

出力例 1

3

一連の操作は、例えば次のように進行します。

  • 箱から取り出したカードに 1 が書かれている。ノートには 1 が 1 個が書かれている状態になる。
  • 箱から取り出したカードに 1 が書かれている。ノートには 1 が 2 個が書かれている状態になる。
  • 箱から取り出したカードに 2 が書かれている。ノートには 1 が 2 個、2 が 1 個書かれている状態になる。

求める期待値は 2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3 です。

入力例 2

5 2
4 1

出力例 2

748683270

求める期待値は \frac{21}{4} であり、\bmod 998244353 で 748683270 となります。

入力例 3

50 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

244742906

求める期待値は \frac{13943237577224054960759}{61980890084919934128} です。

入力例 4

74070 15
1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333

出力例 4

918012973

Score : 625 points

Problem Statement

There are N cards in a box. Each card has an integer written on it, which is between 1 and M, inclusive. For each i=1,\ldots,M, there are C_i cards with the number i written on them.

Starting with an empty notebook, you repeat the following operation:

  • Randomly draw one card from the box. Write the integer on the card in the notebook, then return the card to the box.

Find the expected value, modulo 998244353, of the number of times the operation is performed until the notebook has all integers from 1 to M written at least once.

How to find an expected value modulo 998244353 The expected value sought in this problem can be proven to always be a rational number. Furthermore, the constraints of this problem guarantee that when the expected value is expressed as an irreducible fraction \frac yx, the denominator x is not divisible by 998244353. Then, there is a unique 0\leq z\lt998244353 such that y\equiv xz\pmod{998244353}. Print this z.

Constraints

  • 1 \leq M \leq N \leq 2\times 10^5
  • 1 \leq C_i
  • \sum_{i=1}^{M}C_i=N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
C_1 \ldots C_M

Output

Print the answer.

Sample Input 1

2 2
1 1

Sample Output 1

3

The series of operations may proceed as follows:

  • You draw a card with 1 written on it. The notebook now has one 1 written in it.
  • You again draw a card with 1 written on it. The notebook now has two 1s written in it.
  • You draw a card with 2 written on it. The notebook now has two 1s and one 2 written in it.

The sought expected value is 2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3.

Sample Input 2

5 2
4 1

Sample Output 2

748683270

The expected value is \frac{21}{4}, whose representation modulo 998244353 is 748683270.

Sample Input 3

50 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

244742906

The expected value is \frac{13943237577224054960759}{61980890084919934128}.

Sample Input 4

74070 15
1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333

Sample Output 4

918012973