分数: 500 点
问题陈述
高桥正在参加抽奖。
每次他抽牌,他都会获得以下之一 N 奖品可用。奖品 i 被授予概率 \frac{W_i}{\sum_{j=1}^{N}W_j}。抽签结果是相互独立的。
他得到的概率是多少 M 不同的奖品 K 抽奖?求模 998244353.
注意
要打印有理数,首先将其表示为分数 \frac{y}{x}。 在这里, x 和 y 应该是整数,并且 x 不应被整除 998244353 (在这个问题的约束下,这样的表示总是可能的)。 然后,打印唯一的整数 z 之间 0 和 998244352 (含)使得 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