問題文
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