题目描述

你是一位远近闻名的大法师，你拥有一个药水店，店里有一个容量为 $k$ 单位的炼药锅。

药水店一共经营了 $n$ 天，每天会发生以下的事件恰好一次：

有个初始给定的概率序列 $a_l,a_{l+1}\dots a_r$，表示 $l\sim r$ 被随机选中的概率，保证 $\sum a_i=1$，然后每天会按照 $a$ 带权随机一个整数 $i$。

如果 $i=0$，则什么也不干；

如果 $i<0$，则有一位顾客买走了 $-i$ 单位的药水，你的锅中药水量始终不能小于 $0$；

如果 $i>0$，则大法师向锅内加入了 $i$ 单位的药水，如果超过了锅的容量则加到满为止。

同时你还可以在每天结束时决定是否清空炼药锅。（第一天开始前视作清空过炼药锅）。

药水店的顾客很挑剔，如果他们买到的药水的陈旧度超过 $m$ 天，那么他们就会生气。

药水的陈旧度定义为该日炼药锅距离上一次清空过了多少天，例如，昨天结束时刚清空完炼药锅则今日药水的陈旧度为 $1$（当然，这种情况下今天开始时锅里也没有药水）。

为了维持你的名声，即使某天没有顾客来，你也要保证当天清空前锅里的药水的陈旧度不超过 $m$。

作为一位大法师，你自然不希望有顾客生气。因此对于接下来 $n$ 天的每一种情况，如果你能在预知每天发生的事件的基础下合理清空炼药锅，使得没有人生气，你就认为这种情况是好的。

即，对于一个确定的事件序列 $b_1,b_2,\dots,b_n$（$b_i$ 为第 $i$ 天随机到的整数），你认为他发生的概率是 $\prod_{i=1}^n a_{b_i}$，且你认为他是好的当且仅当存在一种清空炼药锅的方案，使得每天锅里的药水的陈旧度都不超过 $m$，且所有顾客都买到了他需要的药水量。

现在你想知道这 $n$ 天的情况有多大概率是好的，因为你不喜欢实数，所以你只想知道答案对 $998244353$ 取模的结果。

形式化题意：

给定概率序列 $a_l,a_{l+1},\dots,a_r$，保证 $\sum a_i=1$。

考虑所有长为 $n$ 的整数序列 $b_1,b_2,\dots,b_n$，满足 $b_i\in [l,r]$，定义其出现概率为 $\prod_i a_{b_i}$。

定义序列 $b$ 是好的，当且仅当存在 $c_1,c_2\dots,c_n$，满足 $c_i\in \{0,k\}$，使得数列 $s_i=\min(s_{i-1}+b_i,c_i)$ 所有元素 $\geq 0$，且任意连续 $m$ 项都有一项为 $0$，其中 $s_0=0$。

求所有好的 $b$ 序列的出现概率之和对 $998244353$ 取模的结果。

输入格式

第一行输入五个整数 $n,m,k,l,r$。

第二行输入 $r-l+1$ 个整数 $a'_l\sim a'_r$，其中 $a'_i$ 表示实际的 $a_i$ 对 $998244353$ 取模的结果，保证 $\sum a'_i \equiv 1 \pmod{998244353}$。

输出格式

输出一行一个数，表示答案对 $998244353$ 取模的结果。

3 2 1 -1 1
499122177 0 499122177

623902721

10 7 7 -2 2
1 2 3 4 998244344

5347454

10000 6000 11451 -3 3
1 9 1 998244325 9 8 1

45917006

120000 100000 114514 -3 3
875253823 187452905 284279374 460346727 51435610 206896725 929067896

206445697

提示

subtask	$n$	$r-l+1$	特殊性质	分值
$1$	$\leq 10$	$\leq 7$	无	$10$
$2$	$\leq 100$
$3$	$\leq 10^4$			$20$
$4$	$\leq 1.2\times 10^5$	$\leq 3$	$a'_{-1}=a'_1,a'_0=0$	$15$
$5$			无	$10$
$6$	$\leq 6\times 10^4$	$\leq 5$		$15$
$7$	$\leq 1.2 \times 10^5$	$\leq 7$		$20$

对于所有数据：$1\leq m\leq n \leq 1.2\times10^5$，$1\leq k \leq 10^6$，$-3\leq l < 0 < r \leq 3$，$a'_i \in [0,998244353)$，$a'_l,a'_r>0$，$\sum a'_i\equiv 1 \pmod{998244353}$。