[CmdOI2019]算力训练

题目背景

(本题时限经过较大调整,但还是在std耗时的3倍以上,如果觉得卡常数,可以私信出题人) 最近,出题人快乐地学习了如何解一元二次方程。 然而由于一整个暑假的摸鱼,他的计算能力奇差无比,把书上的$5$道例题算错了$3$道。 被怒斥了一番"simple"之后,他开始了算力训练。

题目描述

晚上在宿舍里,出题人梦见了一个使用$k$进制的国度,入乡随俗嘛,出题人在这里也使用$k$进制。 当然,这个国度里面的人也懂数学,所以出题人并没有逃掉算力训练。 他在纸条上写了$n$个$k$进制自然数,由于他很懒,这些数的位数不会太多,都不会超过$m$位。 为了训练算力,他每次会**随意取出一个子序列**(注意可以一个数都不选),然后把这些数都加起来。 他又觉得进位太麻烦了,干脆规定**加法不进位**。 算了几次之后,他突然很想知道自己得到每个数的方案数是多少,可是他太菜了,又不会算,冥思苦想一番之后,突然被起床铃拉出了梦境。 他觉得这个问题很有趣,只好求助于单手虐暴无数代数题的你,来帮忙计算一下。

输入输出格式

输入格式


第一行三个整数$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

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

输出样例 #2

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

输入样例 #3

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

输出样例 #3

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

说明

| 测试点编号 |  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 | **样例解释:** 对于样例1,共有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`。