Cho mảng ~a~ gồm ~n~ phần tử phân biệt và ~2~ số nguyên dương ~k, c~ (~k \leq a_i < 2^c~). Thao tác sau sẽ được thực hiện đúng ~k~ lần:

• Chọn một phần tử bất kỳ trong mảng ~a~ với xác suất bằng nhau. Giảm phần tử đó đi ~\textbf{1}~ đơn vị.

Yêu cầu: Với mỗi ~i~ từ ~0~ đến ~2^c -1~ hãy cho biết xác suất tổng ~XOR~ của mảng ~a = i~ sau khi thực hiện ~k~ thao tác. Có thể chứng minh được các giá trị xác suất trên đều có thể được viết dưới dạng ~\frac{p}{q}~, nên bạn hãy in ra giá trị ~p \cdot q^{-1}\ modulo\ 998244353~ của nó, hay, giá trị nguyên ~x~ (~0 \leq x < 998244353~) sao cho ~x \cdot q \equiv p~ (~mod\ 998244353~).

LƯU Ý: Bài này sẽ được chấm theo thể thức IOI, tức chỉ khi bạn đúng hết các test trong subtask đó thì mới nhận được điểm của cả subtask đó.

Input

• Dòng đầu nhập ~3~ số nguyên dương ~n,k,c~ (~1 \leq n \leq (2^c - k), \ 1 \leq k,\ c \leq 16~).
• Dòng thứ hai nhập vào ~n~ số nguyên dương của mảng ~a~ (~k \leq a_i < 2^c~).

Output

• In ra ~2^c~ số nguyên dương như yêu cầu đề bài.

Subtask

• Subtask 1 ~(15\%)~: ~n \leq 15,\ k \leq 5~.
• Subtask 2 ~(35\%)~: ~c \leq 9~.
• Subtask 3 ~(50\%)~: Không có ràng buộc gì thêm.

Sample

Sample Input 1

3 1 3
4 5 7

Sample Output 1

0 332748118 0 0 0 0 0 665496236

Giải thích: Có ~3~ cách thực hiện thao tác:

• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{3, 5, 7\}~, tổng ~XOR~ là ~1~
• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{4, 4, 7\}~, tổng ~XOR~ là ~7~
• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{4, 5, 6\}~, tổng ~XOR~ là ~7~

Như vậy:

• Xác suất để tổng ~\text{XOR} = 1~ là ~\frac{1}{3}~ nên đáp án là ~332748118~. ~(332748118 \cdot 3 \equiv 1\ (mod\ 998244353))~
• Xác suất để tổng ~\text{XOR} = 7~ là ~\frac{2}{3}~ nên đáp án là ~665496236~. ~{(665496236 \cdot 3 \equiv 2\ (mod\ 998244353))}~
• Các trường hợp khác đều có xác suất là ~0~ nên đáp án là ~0~.