D - Idol Group Costume Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

N 人組アイドルグループのプロデューサーである Motsu-P は、その中の K 人でグループ内ユニットを編成することにしました。強運の持ち主をユニットメンバーに選ぶべく、 K 人のユニットメンバーは、ライブ直前に一様ランダムに選出することにしました。

アイドル i\ (1\leq i\leq N) は、 M_i 個の衣装 1,\ 2,\ldots,M_i を所持しています。新ユニットお披露目ライブには、どの衣装を着てきても良いと彼女たちには伝えたため、彼女たちは各々が持っている衣装の中から一様ランダムに 1 つ選びます。しかし今になって、ユニット衣装は揃っていた方が良いと気付きました。ところがすでにライブ当日であり、今から衣装の変更をすることは間に合いません。Motsu-P の精神安定のために、ユニット衣装が偶然揃っている確率を計算してください。

ただし、ユニット全員の衣装のナンバーが同一であるとき、またそのときに限って、ユニット衣装が揃っているとします。また求める確率は有理数であることが証明できるので、注記で述べるように\bmod 998244353 で出力してください。

出力方法
有理数を出力する際は、まずその有理数を分数  \frac p q として表してください。ここで、p, q は整数であり、q は 998244353 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、 p\equiv qr\pmod{998244353}  を満たすような 0 以上 998244353 未満の唯一の整数 r を出力してください。
ユニットメンバーと衣装の選出方法
ユニットメンバー及び各アイドルが選ぶ衣装は、それぞれ独立に一様ランダムに選ばれる。つまり、ユニットメンバーは {}_N C_K 通りの選び方が、同様に確からしく選出される。さらにそれとは独立にアイドル i が選ぶ衣装は M_i 通りの選び方が、同様に確からしく選出される。

制約

  • 入力は全て整数である。
  • 1 \leq K \leq N \leq 10^5
  • 1 \leq M_i \leq 10^8\ (1\leq i\leq N)

部分点

  • 1 \leq N \leq 2000 を満たすデータセットに正解した場合は 50 点が与えられる。

入力

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

N K
M_1 M_2 \ldots M_N

出力

答えを 1 行に出力せよ。

入力例 1

3 2
1 2 3

出力例 1

55458020

選ばれたアイドルの組を (x,y) のように表すと、ユニット衣装が揃っている確率は、 (1,2) のとき \frac12, (1,3) のとき \frac13 , (2,3) のとき \frac13 であるから、全体として \frac13\left(\frac12+\frac13+\frac13\right)=\frac7{18} となります。\bmod 998244353 で答えることに注意してください。

入力例 2

10 5
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751

出力例 2

819006280