[CmdOI2019] 算力训练

最近，出题人快乐地学习了如何解一元二次方程。 晚上在宿舍里，出题人梦见了一个使用 $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$ 取模。

3 5 1
1 2 3

2
2
1
2
1

5 6 1
1 1 4 5 1 4

8
7
4
2
4
7

### 样例解释 对于样例#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$ |