102435: [AtCoder]ABC243 F - Lottery

Problem Statement

Takahashi is participating in a lottery.

Each time he takes a draw, he gets one of the $N$ prizes available. Prize $i$ is awarded with probability $\frac{W_i}{\sum_{j=1}^{N}W_j}$. The results of the draws are independent of each other.

What is the probability that he gets exactly $M$ different prizes from $K$ draws? Find it modulo $998244353$.

Note

To print a rational number, start by representing it as a fraction $\frac{y}{x}$. Here, $x$ and $y$ should be integers, and $x$ should not be divisible by $998244353$ (under the Constraints of this problem, such a representation is always possible). Then, print the only integer $z$ between $0$ and $998244352$ (inclusive) such that $xz\equiv y \pmod{998244353}$.

Constraints

• $1 \leq K \leq 50$
• $1 \leq M \leq N \leq 50$
• $0 < W_i$
• $0 < W_1 + \ldots + W_N < 998244353$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2 1 2
2
1

Sample Output 1

221832079

Each draw awards Prize $1$ with probability $\frac{2}{3}$ and Prize $2$ with probability $\frac{1}{3}$.

He gets Prize $1$ at both of the two draws with probability $\frac{4}{9}$, and Prize $2$ at both draws with probability $\frac{1}{9}$, so the sought probability is $\frac{5}{9}$.

The modulo $998244353$ representation of this value, according to Note, is $221832079$.

Sample Input 2

3 3 2
1
1
1

Sample Output 2

0

It is impossible to get three different prizes from two draws, so the sought probability is $0$.

Sample Input 3

3 3 10
499122176
499122175
1

Sample Output 3

335346748

Sample Input 4

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

Sample Output 4

755239064

问题描述

高桥正在参加一个抽奖活动。

每次抽奖，他都会得到$N$种奖品中的一种。奖品$i$的获奖概率为$\frac{W_i}{\sum_{j=1}^{N}W_j}$。抽奖的结果是相互独立的。

从$K$次抽奖中，他恰好得到$M$种不同的奖品的概率是多少？答案对$998244353$取模。

注意

要打印一个有理数，首先要将其表示为分数$\frac{y}{x}$。 这里，$x$和$y$应该是整数，且$x$不能被$998244353$整除（在这个问题的约束下，总是可以做到这一点）。 然后，打印介于$0$和$998244352$（含）之间的唯一整数$z$，满足$xz\equiv y \pmod{998244353}$。

约束条件

• $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$

输出

打印答案。

样例输入1

2 1 2
2
1

样例输出1

221832079

每次抽奖，奖品$1$的获奖概率为$\frac{2}{3}$，奖品$2$的获奖概率为$\frac{1}{3}$。

他在两次抽奖中都获得奖品$1$的概率为$\frac{4}{9}$，在两次抽奖中都获得奖品$2$的概率为$\frac{1}{9}$，所以所求概率为$\frac{5}{9}$。

根据注释，这个值对$998244353$取模的表示为$221832079$。

样例输入2

3 3 2
1
1
1

样例输出2

0

从两次抽奖中获得三种不同的奖品是不可能的，所以所求概率为$0$。

样例输入3

3 3 10
499122176
499122175
1

样例输出3

335346748

样例输入4

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

样例输出4

755239064