

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 で出力してください。
出力方法
ユニットメンバーと衣装の選出方法
制約
- 入力は全て整数である。
- 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