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),$$$$$$

where $$$[t_i>0]=1$$$ if $$$t_i>0$$$ and $$$[t_i>0]=0$$$ if $$$t_i=0$$$.

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