题目描述

一天的学习快要结束了，高三楼在晚自习的时候恢复了宁静。
不过，HSD 桑还有一些作业没有完成，他需要在这个晚自习写完。比如这道数学题：

1、给出一个数列，求它的前 $i$ 项和 $S_i$，$i\in \{x|1\le x\le n,x\in \mathbb{N}\}$

HSD 桑擅长数学，很快就把这题秒了……
然而还有第二题：

2、如果把上一问的前 $i$ 项和看成一个新数列，请求出它的前 $i$ 项和

看完第二题，还有第三题……HSD 桑已经预感到情况不妙了。
HSD 桑大致看了看题，发现有些规律。其实就是在求 $k$ 次前缀和。如果我们借用函数迭代的标记，就是在求 $S_n^{(k)}$……
HSD 桑还有很多作业要写，请你帮助他完成这项作业。

输入格式

第一行，两个正整数 $n,k$，$n$ 表示数列的长度，$k$ 的意义如题目描述；
第二行，$n$ 个正整数，表示这个数列，两个数之间用一个空格隔开。

输出格式

共 $n$ 行，每行一个数，第 $i$ 行表示 $S_i^{(k)}$，结果可能会非常大，请对 $998244353$ 取模后输出。

样例

样例输入 1

4 1
1 2 3 4

样例输出 1

1
3
6
10

样例解释 1

对于这个序列，求它的 $1$ 次前缀和，就是输出这个数列的前缀和咯……

样例输入 2

4 3
1 2 3 4

样例输出 2

1
5
15
35

样例解释 2

要求这个数列的 $3$ 次前缀和，这个数列的 $1$ 次前缀和为 $\{1,3,6,10\}$，$2$ 次前缀和为 $\{1,4,10,20\}$，$3$ 次前缀和即为 $\{1,5,15,35\}$。

样例输入 3

见「附加文件」中 one_sample3.in

样例输出 3

见「附加文件」中 one_sample3.ans

数据范围与提示

本题为捆绑测评，只有一组子任务内所有测试点均通过才能获得该子任务的分数。

对于全部数据，保证数列中的任意一个数的范围在 $[0,998244353)$ 内。