[CmdOI2019]算力训练

题目背景

最近,出题人快乐地学习了如何解一元二次方程。 然而由于一整个暑假的摸鱼,他的计算能力奇差无比,把书上的 $5$ 道例题算错了 $3$ 道。 被怒斥了一番 "simple" 之后,他开始了算力训练。

题目描述

晚上在宿舍里,出题人梦见了一个使用 $k$ 进制的国度,入乡随俗嘛,出题人在这里也使用 $k$ 进制。 当然,这个国度里面的人也懂数学,所以出题人并没有逃掉算力训练。 他在纸条上写了 $n$ 个 $k$ 进制自然数,由于他很懒,这些数的位数不会太多,都不会超过 $m$ 位。 为了训练算力,他每次会**随意取出一个子序列**(注意可以一个数都不选),然后把这些数都加起来。 他又觉得进位太麻烦了,干脆规定**加法不进位**。 算了几次之后,他突然很想知道自己得到每个数的方案数是多少,可是他太菜了,又不会算。冥思苦想一番之后,突然被起床铃拉出了梦境。 他觉得这个问题很有趣,只好求助于单手虐暴无数代数题的你,来帮忙计算一下。 **形式化题意** : 对于一个序列 $A$ ,定义其权值 $W(A)$ 为 $A$ 中元素做 $k$ 进制不进位加法的和。 给出 $m,k$ 和一个长为 $n$ 的序列 $S$。保证 $S\subseteq [0,k^m)∩Z$。 对于 $t=0,1,2,...,k^m-1$ ,分别求出下列式子的值 : $${\rm Ans}[t]=\sum\limits_{\text{R 是 S 的子序列}}\big[W(R)=t\big]$$ 注 :根据正确的题意可推知 $\sum\limits_{t=0}^{k^m-1}{\rm Ans}[t]=2^n$。

输入输出格式

输入格式


第一行三个整数 $n,k,m$ ,意义为题目中所述。 第二行 $n$ 个整数,之间用空格隔开,表示纸条上的数字。 (**注意**,纸条上的数均为 $k$ 进制数)

输出格式


共 $k^m$ 行,你需要在第 $i$ 行输出得到数 $i-1$ 的方案数,答案对 $998244353$ 取模。

输入输出样例

输入样例 #1

3 5 1
1 2 3

输出样例 #1

2
2
1
2
1

输入样例 #2

5 6 1
1 1 4 5 1 4

输出样例 #2

8
7
4
2
4
7

输入样例 #3

见 https://www.luogu.org/paste/66c0e63u

输出样例 #3

见 https://www.luogu.org/paste/66c0e63u

输入样例 #4

见 https://www.luogu.org/paste/v1mi6fc5

输出样例 #4

见 https://www.luogu.org/paste/v1mi6fc5

说明

### 样例解释 对于样例#1,共有 $2^3=8$ 种选取子序列的方法: 1. 什么都不选,和为 $0$ 2. 选 $1$ ,和为 $1$ 3. 选 $2$ ,和为 $2$ 4. 选 $3$ ,和为 $3$ 5. 选 $1+2$ ,和为 $3$ 6. 选 $1+3$ ,和为 $4$ 7. 选 $2+3$ ,和为 $0$ (由于是 $5$ 进制,本来要变成 $10$ 的,但是不进位就只剩下 $0$ 了) 8. 选 $1+2+3$,和为 $1$ 综上,得到 `0,1,2,3,4` 的方案数分别是 `2,2,1,2,1` 。 ### 数据范围和约定 | 测试点编号 |  n  |  k  |  m  | 总分数 | | :--: | :--: | :--: | :--: | :--: | | #1 | $20$ | $5$ | $4$ | $5$ | | #2 | $1000$ | $5$ | $4$ | $5$ | | #3~4 | $10^6$ | $5$ | $5$ | $10$ | | #5 | $10^6$ | $5$ | $6$ | $10$ | | #6~7 | $10^6$ | $5$ | $7$ | $20$ | | #8 | $20$ | $6$ | $4$ | $5$ | | #9 | $1000$ | $6$ | $4$ | $5$ | | #10~11 | $10^6$ | $6$ | $4$ | $10$ | | #12~14 | $10^6$ | $6$ | $6$ | $30$ |