Tokitsukaze has a sequence with length of $n$. She likes gems very much. There are $n$ kinds of gems. The gems of the $i$-th kind are on the $i$-th position, and there are $a_i$ gems of the same kind on that position. Define $G(l,r)$ as the multiset containing all gems on the segment $[l,r]$ (inclusive).

A multiset of gems can be represented as $S=[s_1,s_2,\ldots,s_n]$, which is a non-negative integer sequence of length $n$ and means that $S$ contains $s_i$ gems of the $i$-th kind in the multiset. A multiset $T=[t_1,t_2,\ldots,t_n]$ is a multisubset of $S=[s_1,s_2,\ldots,s_n]$ if and only if $t_i\le s_i$ for any $i$ satisfying $1\le i\le n$.

Now, given two positive integers $k$ and $p$, you need to calculate the result of

$$\sum_{l=1}^n \sum_{r=l}^n\sum\limits_{[t_1,t_2,\cdots,t_n] \subseteq G(l,r)}\left(\left(\sum_{i=1}^n p^{t_i}t_i^k\right)\left(\sum_{i=1}^n[t_i \gt 0]\right)\right),$$

where $[t_i \gt 0]=1$ if $t_i \gt 0$ and $[t_i \gt 0]=0$ if $t_i=0$.

Since the answer can be quite large, print it modulo $998\,244\,353$.

Input

The first line contains three integers $n$, $k$ and $p$ ($1\le n \le 10^5$; $1\le k\le 10^5$; $2\le p\le 998\,244\,351$) — the length of the sequence, the numbers $k$ and $p$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 998\,244\,351$) — the number of gems on the $i$-th position.

Output

Print a single integers — the result modulo $998\,244\,353$.