有一个长度为 $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

样例输入 #1

3 2 2
1 1

样例输出 #1

1

样例 1 解释

当两次操作选择的 $x$ 不同时，最终序列为 $[1,2,1]$，序列元素乘积为 $2$；否则序列为 $[2,2,0]$ 或 $[0,2,2]$，序列元素乘积均为 $0$。两次操作选择的 $x$ 不同的概率为 $\frac{1}{2}$ ，因此输出 $2\times \frac{1}{2}=1$。

样例 #2

样例输入 #2

10 3 10
1 2 3 4 5 6 7 8

样例输出 #2

721023399

样例 #3

样例输入 #3

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

样例输出 #3

560770686

子任务

对于所有测试数据，$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\mathrm{\%}$）：$m\le 8$。
• Subtask 2（$20\mathrm{\%}$）：$m\le 16$。
• Subtask 3（$15\mathrm{\%}$）：$n\le 20,c\le n$。
• Subtask 4（$15\mathrm{\%}$）：$n\le 30,c\le n$。
• Subtask 5（$15\mathrm{\%}$）：$n\le 40,c\le n$。
• Subtask 6（$15\mathrm{\%}$）：$c\le n$。
• Subtask 7（$10\mathrm{\%}$）：无特殊限制。