Tokitsukaze and Gems

题意翻译

给定一个长度为 $n$ 的序列 $a$。有 $n$ 种宝石，第 $i$ 种位于第 $i$ 个位置，总数为 $a_i$。我们定义 $G(l,r)$ 为包含位置在 $[l,r]$ 区间内所有宝石的多重集。 我们可以使用一个长度为 $n$ 的非负整数序列 $s$ 来表示一个宝石的多重集，记为 $S = [s_1,s_2,\dots,s_n]$，表示多重集中有 $s_i$ 块第 $i$ 种宝石。一个多重集 $T = [t_1, t_2,\dots,t_n]$ 为 $S = [s_1,s_2,\dots,s_n]$ 的子集，当且仅当 $\ \forall 1\le i \le n, t_i \le s_i$。 现在，给定两个正整数 $k,p$，你需要计算下式： $$\sum_{l=1}^n \sum_{r=l}^n\sum_{[t1,t2,\dots,t_n]\in G(l,r)}\left( \left(\sum_{i=1}^np^{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$ 当且仅当 $t_i = 0$。 由于答案可能会很大，请输出其模 $998244353$ 意义下的值。 $1 \le n\le 10^5, 1\le k \le 10^5, 2\le p \le 998244351, 1\le a_i\le 998244351$。

题目描述

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>0]\right)\right), $ $ </p><p>where $ \[t\_i&gt;0\]=1 $ if $ t\_i&gt;0 $ and $ \[t\_i&gt;0\]=0 $ if $ t\_i=0 $ .</p><p>Since the answer can be quite large, print it modulo $ 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.

输出格式

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

输入输出样例

输入样例 #1

5 2 2
1 1 1 2 2

输出样例 #1

6428

输入样例 #2

6 2 2
2 2 2 2 2 3

输出样例 #2

338940