#6261. 一个人的高三楼

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

题目描述

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

1、给出一个数列,求它的前 ii 项和 SiS_ii{x1xn,xN}i\in \{x|1\le x\le n,x\in \mathbb{N}\}

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

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

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

输入格式

第一行,两个正整数 n,kn,knn 表示数列的长度,kk 的意义如题目描述;
第二行,nn 个正整数,表示这个数列,两个数之间用一个空格隔开。

输出格式

nn 行,每行一个数,第 ii 行表示 Si(k)S_i^{(k)},结果可能会非常大,请对 998244353998244353 取模后输出。

样例

样例输入 1

4 1
1 2 3 4

样例输出 1

1
3
6
10

样例解释 1

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

样例输入 2

4 3
1 2 3 4

样例输出 2

1
5
15
35

样例解释 2

要求这个数列的 33 次前缀和,这个数列的 11 次前缀和为 {1,3,6,10}\{1,3,6,10\}22 次前缀和为 {1,4,10,20}\{1,4,10,20\}33 次前缀和即为 {1,5,15,35}\{1,5,15,35\}

样例输入 3

见「附加文件」中 one_sample3.in

样例输出 3

见「附加文件」中 one_sample3.ans

数据范围与提示

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

Subtask 分数 nn kk
11 2020 103\le 10^3 102\le 10^2
22 3030 105\le 10^5 218\le 2^{18}
33 5050 105\le 10^5 260\le 2^{60}

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