CF1677F.Tokitsukaze and Gems

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$.

Tokitsukaze 有一个长度为 $n$ 的序列。她非常喜欢宝石。一共有 $n$ 种宝石，第 $i$ 种宝石位于第 $i$ 个位置，该位置上有 $a_i$ 颗同种宝石。定义 $G(l,r)$ 为区间 $[l,r]$（含端点）上所有宝石构成的多重集。

一个宝石多重集可表示为 $S=[s_1,s_2,\ldots,s_n]$，即一个长度为 $n$ 的非负整数序列，其含义是：多重集 $S$ 中包含 $s_i$ 颗第 $i$ 种宝石。多重集 $T=[t_1,t_2,\ldots,t_n]$ 是多重集 $S=[s_1,s_2,\ldots,s_n]$ 的多重子集，当且仅当对任意满足 $1\le i\le n$ 的 $i$，均有 $t_i\le s_i$。

现给定两个正整数 $k$ 和 $p$，你需要计算下列表达式的值：

$$\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 > 0]\right)\right),$$

其中 $[t_i > 0]=1$ 当 $t_i > 0$，否则 $[t_i > 0]=0$。

由于答案可能非常大，请将结果对 $998\,244\,353$ 取模后输出。

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.

第一行包含三个整数 $n$、$k$ 和 $p$（$1\le n \le 10^5$；$1\le k\le 10^5$；$2\le p\le 998\,244\,351$）—— 分别表示序列长度、数字 $k$ 和 $p$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 998\,244\,351$）—— 表示第 $i$ 个位置上的宝石数量。

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

输出一个整数——结果对 $998\,244\,353$ 取模的值。