Problem Background

(The above image is reproduced from a description by a certain deity)

Little K is daydreaming again. He has entered his fantasy world and found a very interesting sequence \(a\) and a very interesting number \(k\).

Problem Description

We denote the \(k\)-th order sub-segment sum of a sequence \([l, r]\) 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 currently standing at position 1. Each time he expands to the right by one cell, his luck in the IOI contest increases, so he wants to expand as much as possible. However, each time he expands from \(r\) to \(r+1\), he needs to correctly answer \(sum_{k,1,r}\). Little K is too lazy to calculate, so he assigns the task to you.

Input Format

Two lines. The first line contains \(n\) and \(k\), representing the length of \(a\) and \(k\) respectively.

The second line contains \(n\) positive integers, representing the sequence \(a\).

Output Format

One line, where the \(i\)-th number is \(sum_{k,1,i}\). Since the answer can be very large, you only need to output the result modulo \(998244353\).

Sample Input and Output

Sample Input #1

3 1
1 2 3

Sample Output #1

1 3 6

Sample Input #2

3 2
1 2 3

Sample Output #2

1 6 20

Sample Input #3

3 10
1 2 3

Sample Output #3

1 30 420

Notes

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 \]

Data Range

见题面 Input 部分

见题面 Output 部分