У 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]$$$ тогда и только тогда, когда $$$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]=1$$$, если $$$t_i>0$$$ и $$$[t_i>0]=0$$$, если $$$t_i=0$$$.

Так как ответ может быть довольно большим, выведите его по модулю $$$998\,244\,353$$$.