У 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\).