Description

The problem setter wrote down $n$ base-$k$ natural numbers on a slip of paper. Because he is lazy, these numbers will not have too many digits, and none of them exceeds $m$ digits.

To train computing power, each time he will randomly pick a subsequence (it is allowed to pick none), and then add all the chosen numbers together.

He also felt carrying was too troublesome, so he simply规定 that addition is done without carry.

After computing a few times, he suddenly wanted to know how many ways he can obtain each number, but he is too weak and cannot compute it. After thinking hard, he was suddenly pulled out of the dream by the wake-up bell.

He found this problem interesting, so he had to ask you, who can crush countless algebra problems with one hand, to help compute it.

Formal statement: For a sequence $A$, define its weight $W(A)$ as the sum of the elements in $A$ using base-$k$ addition without carry.

Given $m$, $k$, and a sequence $S$ of length $n$. It is guaranteed that $S\subseteq [0,k^m)∩Z$.

For $t=0,1,2,...,k^m-1$, compute the value of:

$${\rm Ans}[t]=\sum\limits_{\text{R is a subsequence of S}}\big[W(R)=t\big]$$

Note: From the correct statement, we can infer that $\sum\limits_{t=0}^{k^m-1}{\rm Ans}[t]=2^n$.

Input Format

The first line contains three integers $n,k,m$, with the meaning described in the statement.

The second line contains $n$ integers separated by spaces, representing the numbers on the slip of paper.

(Note: the numbers on the slip of paper are all base-$k$ numbers.)

Output Format

There are $k^m$ lines. On the $i$-th line, output the number of ways to obtain the number $i-1$. Output the answer modulo $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

Hint

Sample Explanation

For Sample #1, there are $2^3=8$ ways to choose a subsequence:

1. Choose nothing, the sum is $0$.
2. Choose $1$, the sum is $1$.
3. Choose $2$, the sum is $2$.
4. Choose $3$, the sum is $3$.
5. Choose $1+2$, the sum is $3$.
6. Choose $1+3$, the sum is $4$.
7. Choose $2+3$, the sum is $0$ (since it is base $5$, it should become $10$, but without carry it becomes only $0$).
8. Choose $1+2+3$, the sum is $1$.

In summary, the numbers of ways to obtain 0,1,2,3,4 are 2,2,1,2,1, respectively.

Constraints and Conventions

Test Point ID	n	k	m	Total Score
#1	$20$	$5$	$4$	$5$
#2	$1000$
#3~4	$10^6$		$5$	$10$
#5			$6$
#6~7			$7$	$20$
#8	$20$	$6$	$4$	$5$
#9	$1000$
#10~11	$10^6$			$10$
#12~14			$6$	$30$

Translated by ChatGPT 5