题目描述

高橋君はくじを引こうとしています。

くじを $1$ 回引くごとに、$N$ 種類の賞品のいずれかが手に入ります。賞品 $i$ が手に入る確率は $\frac{W_i}{\sum_{j=1}^{N}W_j}$ であり、各くじの結果は独立です。

くじを $K$ 回引いたとき、ちょうど $M$ 種類の賞品が手に入る確率はいくらでしょうか？ $\bmod\ 998244353$ で求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $W_1$ $\vdots$ $W_N$

输出格式

答えを出力せよ。

题目大意

一个游戏的抽卡池里有 $n$ 种角色，每种角色的数量无限多，第 $i$ 个角色被抽出的概率是 $\frac{W_i}{\sum_{j=1}^{n}W_j}$，你的钱包只够你氪金抽 $k$ 次，问你最后恰好抽到 $m$ 种不同的角色的概率是多少，答案对 $998244353$ 取模。

2 1 2
2
1

221832079

3 3 2
1
1
1

0

3 3 10
499122176
499122175
1

335346748

10 8 15
1
1
1
1
1
1
1
1
1
1

755239064

提示

注記

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。 ここで、$x,y$ は整数であり、$x$ は $998244353$ で割り切れてはなりません（この問題の制約下で、そのような表現は必ず可能です）。 そして、$xz\equiv\ y\ \pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の唯一の整数 $z$ を出力してください。

制約

• $1\ \leq\ K\ \leq\ 50$
• $1\ \leq\ M\ \leq\ N\ \leq\ 50$
• $0\ <\ W_i$
• $0\ <\ W_1\ +\ \ldots\ +\ W_N\ <\ 998244353$
• 入力は全て整数である

Sample Explanation 1

各くじの結果として、賞品 $1$ が手に入る確率が $\frac{2}{3}$、賞品 $2$ が手に入る確率が $\frac{1}{3}$ です。 $2$ 回のくじの結果として、ともに賞品 $1$ を手に入れる確率が $\frac{4}{9}$、ともに賞品 $2$ を手に入れる確率が $\frac{1}{9}$ であるため、求める答えは $\frac{5}{9}$ です。 これを注記にしたがって $\bmod\ 998244353$ で出力すると $221832079$ になります。

Sample Explanation 2

くじを $2$ 回引いて $3$ 種類の賞品を手に入れることはできません。したがって求める確率は $0$ です。