重返现世

题目描述

为了打开返回现世的大门,Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 $n$ 种原料,只需要集齐任意 $k$ 种,就可以开始制作。 Yopilla 来到了迷失大陆的核心地域。每个单位时间,这片地域就会随机生成一种原料。每种原料被生成的概率是不同的,第 $i$ 种原料被生成的概率是 $\frac{p_i}{m}$ 。如果 Yopilla 没有这种原料,那么就可以进行收集。 Yopilla 急于知道,他收集到任意 $k$ 种原料的期望时间,答案对 $998244353$ 取模。

输入输出格式

输入格式


第一行三个数 $n, k, m$ 。 第二行 $n$ 个数 $p_1, p_2, ..., p_n$ 。

输出格式


输出一行。

输入输出样例

输入样例 #1

3 3 3
1 1 1

输出样例 #1

499122182

说明

对于 $10 \%$ 的数据,$p_1 = p_2 = ... = p_m$ 。 对于另外 $10 \%$ 的数据,$k = n$ 。 对于 $70 \%$ 的数据,$n \le 100$ 。 对于 $100 \%$ 的数据,$1 \le n \le 1000$ ,$1 \le k \le n, \lvert n - k \rvert \le 10$ ,$0 \le p_i \le m, \sum p = m, 1 \le m \le 10000$ 。