#6261. 一个人的高三楼

内存限制:256 MiB 时间限制:200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

一天的学习快要结束了,高三楼在晚自习的时候恢复了宁静。
不过,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

数据范围与提示

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

Subtask 分数 n k
1 20 \le 10^3 \le 10^2
2 30 \le 10^5 \le 2^{18}
3 50 \le 2^{60}

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