F. Tokitsukaze и драгоценные камни
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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$$$.

Входные данные

Первая строка содержит три целых числа $$$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$$$.

Примеры
Входные данные
5 2 2
1 1 1 2 2
Выходные данные
6428
Входные данные
6 2 2
2 2 2 2 2 3
Выходные данные
338940