AT_abc243_f [ABC243F] Lottery

高桥君打算抽奖。 每抽一次奖，就会获得 $N$ 种奖品中的某一种。获得第 $i$ 种奖品的概率为 $\frac{W_i}{\sum_{j=1}^{N}W_j}$，且每次抽奖的结果相互独立。 当抽奖 $K$ 次时，恰好获得 $M$ 种不同奖品的概率是多少？请将答案对 $998244353$ 取模后输出。

输入从标准输入中按以下格式给出。 > $N$ $M$ $K$ $W_1$ > $W_2$ > $\vdots$ > $W_N$

请输出答案。

### 注记 输出有理数时，首先将其表示为分数 $\frac{y}{x}$，其中 $x, y$ 均为整数，且 $x$ 不能被 $998244353$ 整除（在本题的约束下，总能做到）。然后，输出唯一满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$ 的整数 $z$。 ### 约束条件 - $1 \leq K \leq 50$ - $1 \leq M \leq N \leq 50$ - $0 < W_i$ - $0 < W_1 + \ldots + W_N < 998244353$ - 所有输入均为整数 ### 样例解释 1 每次抽奖获得奖品 $1$ 的概率为 $\frac{2}{3}$，获得奖品 $2$ 的概率为 $\frac{1}{3}$。两次抽奖都获得奖品 $1$ 的概率为 $\frac{4}{9}$，都获得奖品 $2$ 的概率为 $\frac{1}{9}$，因此答案为 $\frac{5}{9}$。按照注记的要求对 $998244353$ 取模后输出 $221832079$。 ### 样例解释 2 抽奖 $2$ 次无法获得 $3$ 种不同的奖品，因此概率为 $0$。 由 ChatGPT 4.1 翻译