P11420 [清华集训 2024] 乘积的期望

有一个长度为 $n$ 的序列 $a_1, a_2, \cdots , a_n$。初始序列的所有元素均为 $0$。再给定正整数 $m$、$c$ 和 $(n - m + 1)$ 个正整数 $b_1, b_2, \cdots , b_{n−m+1}$。 对序列 $a_1, a_2, \cdots , a_n$ 进行 $c$ 次操作，每次操作为： - 随机选择整数 $1 \le x \le n - m + 1$，其中选到 $y$（$1\le y\le n-m+1$）的概率为 $\displaystyle \frac{b_y}{\sum_{i=1}^{n-m+1} b_i}$。将 $a_x, a_{x+1}, \cdots, a_{x+m−1}$ 增加 $1$。 $c$ 次操作中对 $x$ 的随机是独立的。 求操作完成后序列中所有元素的乘积的期望。为了避免浮点数输出，你需要将答案对 $998244353$ 取模。

从标准输入读入数据。 第一行三个整数 $n, m, c$，分别表示序列长度、操作区间长度和操作次数。 第二行 $(n - m + 1)$ 个整数 $b_1, \cdots , b_{n-m+1}$，描述随机的权重。

输出到标准输出。 输出一行一个整数，表示 $c$ 次操作后序列中所有数的乘积的期望。

#### 【样例 $1$ 解释】 当两次操作选择的 $x$ 不同时，最终序列为 $[1,2,1]$，序列元素乘积为 $2$；否则序列为 $[2,2,0]$ 或 $[0,2,2]$，序列元素乘积均为 $0$。两次操作选择的 $x$ 不同的概率为 $\frac{1}{2}$ ，因此输出 $2\times \frac{1}{2}=1$。 #### 子任务 对于所有测试数据，$2 \le m \le n \le 50$，$1 \le c < 998244353$，对于 $1 \le i \le n - m + 1$，$1 \le b_i \le 10^5$。 - Subtask 1（$10\%$）：$m \le 8$。 - Subtask 2（$20\%$）：$m \le 16$。 - Subtask 3（$15\%$）：$n \le 20, c \le n$。 - Subtask 4（$15\%$）：$n \le 30, c \le n$。 - Subtask 5（$15\%$）：$n \le 40, c \le n$。 - Subtask 6（$15\%$）：$c \le n$。 - Subtask 7（$10\%$）：无特殊限制。