[ABC243F] Lottery

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

[problemUrl]: https://atcoder.jp/contests/abc243/tasks/abc243_f 高橋君はくじを引こうとしています。 くじを $ 1 $ 回引くごとに、$ N $ 種類の賞品のいずれかが手に入ります。賞品 $ i $ が手に入る確率は $ \frac{W_i}{\sum_{j=1}^{N}W_j} $ であり、各くじの結果は独立です。 くじを $ K $ 回引いたとき、ちょうど $ M $ 種類の賞品が手に入る確率はいくらでしょうか？ $ \bmod\ 998244353 $ で求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ W_1 $ $ \vdots $ $ W_N $

答えを出力せよ。

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 $ です。