题面描述

你是一位远近闻名的大法师，你拥有一个药水店，店里有一个容量为 $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)$ 所有元素 $\ge 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 , (\text{mod} , 998244353)$。

输出格式

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

输入输出样例

样例 1 输入：

3 2 1 -1 1
499122177 0 499122177

样例 1 输出：

623902721

样例 1 解释：

实际的 $a_{-1}, a_0, a_1$ 为 $\frac{1}{2}, 0, \frac{1}{2}$。

有以下三种好的情况：

1. 第一天向锅里加入 $1$ 单位药水，第二天有一位顾客想买 $1$ 单位药水，第三天向锅里加入 $1$ 单位药水。这种情况下你不需要清空。
2. 第一天向锅里加入 $1$ 单位药水，第二天向锅里加入 $1$ 单位药水，第三天有一位顾客想买 $1$ 单位药水。这种情况下在第一天结束后需要清空，否则第三天时药水陈旧度为 $3$。
3. 第一天向锅里加入 $1$ 单位药水，第二天向锅里加入 $1$ 单位药水，第三天向锅里加入 $1$ 单位药水。这种情况下在第一天结束后需要清空，否则第三天时药水陈旧度为 $3$。

每种情况发生的概率都是 $\frac{1}{8}$，所以答案是 $\frac{3}{8} \equiv 623902721 , (\text{mod} , 998244353)$。

样例 2 输入：

10 7 7 -2 2
1 2 3 4 998244344

样例 2 输出：

5347454

样例 3 输入：

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

样例 3 输出：

45917006

样例 4 输入：

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

样例 4 输出：

206445697

数据范围

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