彩票

题目描述

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

每次抽奖,他会获得 $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$,其中 $0 \le z \le 998244352$。

输入格式

输入按以下格式从标准输入给出:

N M K
W_1
⋮
W_N

输出格式

输出答案。

样例

2 1 2
2
1

221832079

每次抽奖以 $\frac{2}{3}$ 的概率抽中奖品 $1$,以 $\frac{1}{3}$ 的概率抽中奖品 $2$。

两次抽奖都以 $\frac{4}{9}$ 的概率抽中奖品 $1$,以 $\frac{1}{9}$ 的概率抽中奖品 $2$,因此所求概率为 $\frac{5}{9}$。

根据「注」,该值对 $998244353$ 取模的表示是 $221832079$。

3 3 2
1
1
1

0

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

3 3 10
499122176
499122175
1

335346748

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

755239064

数据范围

• $1 \le K \le 50$
• $1 \le M \le N \le 50$
• $0 \lt W_i$
• $0 \lt W_1 + \ldots + W_N \lt 998244353$
• 输入中的所有值均为整数。