Tokitsukaze 的序列长度为 $$$n$$$。她非常喜欢宝石。宝石有 $$$n$$$ 种。第 $$$i$$$ 种宝石位于第 $$$i$$$ 位置,并且该位置上有 $$$a_i$$$ 同类宝石。将 $$$G(l,r)$$$ 定义为包含段 $$$[l,r]$$$(包含)上所有宝石的多重集。
宝石的多重集可以表示为 $$$S=[s_1,s_2,\ldots,s_n]$$$,它是长度为 $$$n$$$ 的非负整数序列,意味着 $$$S$$$ 包含多重集中第 $$$i$$$ 种的 $$$s_i$$$ 宝石。多重集 $$$T=[t_1,t_2,\ldots,t_n]$$$ 是 $$$S=[s_1,s_2,\ldots,s_n]$$$ 的多重子集当且仅当 $$$t_i\le s_i$$$ 对于任何 $$$i$$$ 满足 $$$1\le i\le n$$$。
现在,给定两个正整数 $$$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$$$,则 $$$[t_i>0]=1$$$;如果 $$$t_i=0$$$,则 $$$[t_i>0]=0$$$。
由于答案可能相当大,因此打印它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含三个整数 $$$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$$$ 位置上的宝石数量。
输出
打印单个整数 - 结果以 $$$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