AT_utpc2020_d Idol Group Costume

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_d $ 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 $ 通りの選び方が、同様に確からしく選出される。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ M_1 $ $ M_2 $ $ \ldots $ $ M_N $

答えを $ 1 $ 行に出力せよ。

### 制約 - 入力は全て整数である。 - $ 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 $ 点が与えられる。 ### Sample Explanation 1 選ばれたアイドルの組を $ (x,y) $ のように表すと、ユニット衣装が揃っている確率は、 $ (1,2) $ のとき $ \frac12 $, $ (1,3) $ のとき $ \frac13 $ , $ (2,3) $ のとき $ \frac13 $ であるから、全体として $ \frac13\left(\frac12+\frac13+\frac13\right)=\frac7{18} $ となります。$ \bmod\ 998244353 $ で答えることに注意してください。