配点 : $500$ 点

問題文

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

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

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

注記

有理数を出力する際は、まずその有理数を分数 $\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$
• 入力は全て整数である

入力

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

$N$ $M$ $K$

$W_1$

$\vdots$

$W_N$

出力

答えを出力せよ。

2 1 2
2
1

221832079

各くじの結果として、賞品 $1$ が手に入る確率が $\frac{2}{3}$、賞品 $2$ が手に入る確率が $\frac{1}{3}$ です。

$2$ 回のくじの結果として、ともに賞品 $1$ を手に入れる確率が $\frac{4}{9}$、ともに賞品 $2$ を手に入れる確率が $\frac{1}{9}$ であるため、求める答えは $\frac{5}{9}$ です。

これを注記にしたがって $\bmod 998244353$ で出力すると $221832079$ になります。

3 3 2
1
1
1

0

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

3 3 10
499122176
499122175
1

335346748

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

755239064