题目描述

问题陈述

Takahashi 正在参加一场抽奖活动。

每次他参与抽奖，都有机会获得 $N$ 个奖品中的一个。第 $i$ 个奖品的概率是 $\\frac{W_i}{\\sum_{j=1}^{N}W_j}$。每次抽奖结果之间是相互独立的。

在 $K$ 次抽奖中，他恰好获得 $M$ 个不同的奖品的概率是多少？求其对 $998244353$ 取模的结果。

注意事项

为了输出一个有理数，请首先将其表示为分数 $\\frac{y}{x}$ 的形式。其中，$x$ 和 $y$ 是整数，并且 $x$ 不可被 $998244353$ 整除（在本问题的约束条件下，总可以找到这样的表示）。然后，输出满足性质 $xz\\equiv y \\pmod{998244353}$ 的唯一整数 $z$，其中 $z$ 的取值范围是 $0$ 到 $998244352$（包括边界）。

约束条件

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