409009: GYM103415 A Math Ball

Cake has $$$n$$$ types of balls numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th type of which has a sufficient number of indistinguishable balls and a cost $$$c_i$$$. Cake wants to take away some of them, but his backpack can only carry at most $$$W$$$ balls. Simple knapsack problem cannot please Cake, so he wants to add some magic to the balls. Formally, if he takes $$$k_i$$$ balls from the $$$i$$$-th type, the cost is $$$C=k_1^{c_1}k_2^{c_2}\ldots k_n^{c_n}$$$. We wants know for all possible plans taking at most $$$W$$$ balls, what the total cost modulo 998244353 is.

First line contains two integers $$$n$$$ and $$$W$$$, and the second line contains $$$n$$$ integers $$$c_1, c_2, \ldots c_n$$$, separated by space.

It is guaranteed that $$$n\le 10^5$$$, $$$W\le 10^{18}$$$, and $$$\sum c_i\le 10^5$$$.

Print the total cost modulo 998244353.

4 5
1 2 3 4

31

For the sample input, plans $$$(k_1,k_2,k_3,k_4)$$$ with non-zero costs are $$$(1, 1, 1, 2)$$$, $$$(1, 1, 2, 1)$$$, $$$(1, 2, 1, 1)$$$, $$$(2, 1, 1, 1)$$$, and $$$(1, 1, 1, 1)$$$, and the total cost is $$$2^4+2^3+2^2+2^1+1=31$$$.