题目描述

有一个长度为 $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$ 次操作后序列中所有数的乘积的期望。

3 2 2
1 1

1

10 3 10
1 2 3 4 5 6 7 8

721023399

20 12 98765
9 8 7 6 5 4 3 2 1

560770686

提示

【样例 $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\%$）：无特殊限制。