Background

(The picture above is reposted from a certain expert’s problem statement.)

Little K is daydreaming again. In his fantasy, he found a very interesting sequence $a$ and a very interesting number $k$.

Problem Description

For a sequence interval $[l,r]$, we define its $k$-th order subsegment sum as $sum_{k,l,r}$, where

$$sum_{k,l,r}=\begin{cases}\sum\limits_{i=l}^{r}a_i&,k=1\\\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}sum_{k-1,i,j}&,k\geq 2\end{cases}$$

He is now standing at position $1$. Each time he expands one cell to the right, he can increase his rp on the IOI contest field, so he wants to expand as many cells as possible. However, every time he expands from $r$ to $r+1$, he needs to correctly answer $sum_{k,1,r}$. Little K cannot be bothered to calculate it, so he leaves the task to you.

Input Format

Two lines. The first line contains $n,k$, representing the length of $a$ and $k$.

The second line contains $n$ positive integers, representing $a$.

Output Format

One line. The $i$-th number is $sum_{k,1,i}$. Since the answer is too large, you only need to output the value modulo $998244353$.

3 1
1 2 3

1 3 6

3 2
1 2 3

1 6 20

3 10
1 2 3

1 30 420

Hint

Sample Explanation 2

$sum_{2,1,1}=sum_{1,1,1}=1$

$sum_{2,1,2}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,2,2}=1+3+2=6$

$sum_{2,1,3}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,1,3}+sum_{1,2,2}+sum_{1,2,3}+sum_{1,3,3}=1+3+6+2+5+3=20$

Constraints

Test Point ID	Range of $n$	Range of $k$	Range of $a_i$
$1\sim 2$	$\le 10$
$3\sim 8$	$\le 10^3$		$\le 10^5$
$9$	$\le 10^5$	$=1$	$\le 998244353$
$10$		$=2$
$11$		$=3$
$12$		$\le 10$
$13\sim 17$		$\le 10^2$
$18$		$\le 10^5$
$19\sim 25$		$\le 998244353$

Translated by ChatGPT 5