You are a renowned archmage who owns a potion shop with a cauldron that has a capacity of $k$ units.

The potion shop has been operating for $n$ days, and exactly one event occurs each day:

There is an initially given probability sequence $a_l, a_{l+1}, \dots, a_r$, representing the probability that $l \sim r$ is selected, with $\sum a_i = 1$. Each day, an integer $i$ is randomly chosen according to the weighted probabilities $a$.

If $i = 0$, nothing happens.

If $i < 0$, a customer buys $-i$ units of potion. The amount of potion in your cauldron must never be less than $0$.

If $i > 0$, the archmage adds $i$ units of potion to the cauldron. If the amount exceeds the capacity, it is filled to the maximum capacity $k$.

Additionally, you can decide whether to empty the cauldron at the end of each day (the cauldron is considered empty before the first day begins).

The customers at the potion shop are very picky; if the age of the potion they purchase exceeds $m$ days, they will become angry.

The age of the potion is defined as the number of days that have passed since the last time the cauldron was emptied. For example, if the cauldron was just emptied at the end of yesterday, the age of the potion today is $1$ (of course, in this case, there is no potion in the cauldron at the start of today).

To maintain your reputation, even if no customer comes on a certain day, you must ensure that the age of the potion in the cauldron before emptying it that day does not exceed $m$.

As an archmage, you naturally do not want any customers to get angry. Therefore, for each of the next $n$ days, if you can reasonably empty the cauldron given the knowledge of the events occurring each day such that no one gets angry, you consider this situation to be "good."

That is, for a fixed sequence of events $b_1, b_2, \dots, b_n$ (where $b_i$ is the integer randomly chosen on day $i$), you consider its probability to be $\prod_{i=1}^n a_{b_i}$, and you consider it "good" if and only if there exists a strategy for emptying the cauldron such that the age of the potion in the cauldron never exceeds $m$ on any day, and all customers receive the amount of potion they require.

Now you want to know the total probability that the situation over these $n$ days is "good." Since you do not like real numbers, you only want to know the result modulo $998244353$.

Formal Problem Statement:

Given a probability sequence $a_l, a_{l+1}, \dots, a_r$, where $\sum a_i = 1$.

Consider all integer sequences $b_1, b_2, \dots, b_n$ of length $n$ such that $b_i \in [l, r]$, and define their probability of occurrence as $\prod_i a_{b_i}$.

A sequence $b$ is defined as "good" if and only if there exist $c_1, c_2, \dots, c_n$ with $c_i \in \{0, k\}$ such that for the sequence $s_i = \min(s_{i-1} + b_i, c_i)$, all elements are $\ge 0$, and any $m$ consecutive terms contain at least one $0$, where $s_0 = 0$.

Calculate the sum of the probabilities of all "good" $b$ sequences, modulo $998244353$.

Input

The first line contains five integers $n, m, k, l, r$.

The second line contains $r - l + 1$ integers $a'_l \sim a'_r$, where $a'_i$ represents the actual $a_i$ modulo $998244353$, ensuring $\sum a'_i \equiv 1 \pmod{998244353}$.

Output

Output a single integer representing the answer modulo $998244353$.

Examples

Input 1

3 2 1 -1 1
499122177 0 499122177

Output 1

623902721

Note 1

The actual values of $a_{-1}, a_0, a_1$ are $\frac{1}{2}, 0, \frac{1}{2}$.

There are three "good" scenarios:

1. Add $1$ unit of potion on the first day, a customer buys $1$ unit on the second day, and add $1$ unit on the third day. In this case, you do not need to empty the cauldron.
2. Add $1$ unit of potion on the first day, add $1$ unit on the second day, and a customer buys $1$ unit on the third day. In this case, you must empty the cauldron at the end of the first day; otherwise, the age of the potion on the third day would be $3$.
3. Add $1$ unit of potion on the first day, add $1$ unit on the second day, and add $1$ unit on the third day. In this case, you must empty the cauldron at the end of the first day; otherwise, the age of the potion on the third day would be $3$.

The probability of each scenario is $\frac{1}{8}$, so the answer is $\frac{3}{8} \equiv 623902721 \pmod{998244353}$.

Input 2

10 7 7 -2 2
1 2 3 4 998244344

Output 2

5347454

Input 3

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

Output 3

45917006

Input 4

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

Output 4

206445697

Constraints

For all data: $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 \pmod{998244353}$.