P16782 ⌈Xzy OI R1 T4⌋ Eating Shaved Ice.

**The input size of this problem is large. Please choose a suitable input method.** For each partial score level of this problem, the time limit is $1.5\sim2$ times that of the corresponding std. If your solution cannot pass, please check whether your time complexity is correct. > @Nuclear_Fish_cyq : I【】really【】feel magical. || @Nuclear_Fish_cyq : If this problem is not fake, I will name it drug, because it is too magical.

Ziyaqiu is on a grid with $n$ rows, and its initial coordinate is $(0,0)$. The last row has $m(n-1)+1$ shaved ices. Each shaved ice has an attribute called “deliciousness”, which are $a_1,a_2,\cdots ,a_{m(n-1)+1}$. Now Ziyaqiu wants to start from $(0,0)$ and walk $n-1$ steps. In each step, Ziyaqiu moves down by $1$ cell, and then it can choose any number $k$ in $[0,m]$ and move right by $k$ cells. Obviously, Ziyaqiu can always end up on a shaved ice. Different walking plans may lead to different or the same deliciousness. Ziyaqiu wants you to compute the sum of the deliciousness values brought by all walking plans, modulo $998244353$.

The first line contains two positive integers $n,m$. The next line contains $m(n-1)+1$ integers, representing the deliciousness of the shaved ices in the last row.

Output one positive integer in one line, representing the answer.

**Constraints** **This problem uses bundled testdata, i.e. you must pass all test points in a subtask to get the score for that subtask.** ::cute-table{tuack} | Subtask | Score | $1 \le n \le$ | $1 \le m \le$ | Time limit | |:-:|:-:|:-:|:-:|:-:| |$1$|$20$|$100$| $100$ | 2000ms | |$2$|$30$|$10^4$| ^ | ^ | |$3$|$20$|^| ^ | 750ms | |$4$|$30$|^| ^ | 125ms | For $100\%$ of the data, $-10^8\leq a_i\leq 10^8$. Translated by ChatGPT 5