P12492 [集训队互测 2024] 药水

你是一位远近闻名的大法师，你拥有一个药水店，店里有一个容量为 $k$ 单位的炼药锅。 药水店一共经营了 $n$ 天，每天会发生以下的事件恰好一次： **有个初始给定的概率序列 $a_l,a_{l+1}\dots a_r$，表示 $l\sim r$ 被随机选中的概率，保证 $\sum a_i=1$，然后每天会按照 $a$ 带权随机一个整数 $i$。** **如果 $i=0$，则什么也不干；** **如果 $i0$，则大法师向锅内加入了 $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$ 取模的结果。

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