Background

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.

Problem Description

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

Input Format

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 Format

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

4 3
0 1 2 3 4 5 6 7 8 9

288

2 1
1 -1

0

Hint

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}

For $100\%$ of the data, $-10^8\leq a_i\leq 10^8$.

Translated by ChatGPT 5