There is a lottery that is going to happen and $$$n$$$ ($$$1 \le n \le 10^6$$$) people have already bought one or more lottery tickets: the $$$i$$$th person has bought $$$t_i$$$ ($$$1 \le t_i \le 5$$$) lottery tickets. There will be $$$m$$$ ($$$1 \le m \le \min{\left( 100, n \right)}$$$) draws. In the $$$j$$$-th ($$$1 \le j \le m$$$) draw:
Alice is the last (that is, the $$$n+1$$$-th) ticket buyer, and she wants to win the $$$k$$$-th prize ($$$1 \le k \le m$$$). Alice can buy between $$$1$$$ to $$$l$$$ ($$$1 \le l \le 2000$$$) lottery tickets (inclusive range). She wants to know, for each $$$x \in \{ 1, \dots, l \}$$$, what the probability for winning the $$$k$$$-th prize is if she buys exactly $$$x$$$ tickets.
Alice has figured out that the probability $$$f(x)$$$ of winning the first prize is given by $$$$$$ f(x) = \sum_{\substack{A \subseteq \{ 1, \dots, n\} \\ |A| \le m - 1}} \left( -1 \right)^{m - 1 - |A|} {{n - |A|}\choose{m - 1 - |A|}} \left( \frac{x}{x + \sum_{j \not\in A} t_j} \right) $$$$$$
Alice has asked you to figure out the rest.
The first line contains four space-separated integers $$$n, m, k, l$$$. The next line contains $$$n$$$ space-separated integers $$$t_1, \dots, t_n$$$.
For each $$$i \in \{1, \dots, l\}$$$, the probability that Alice wins the $$$k$$$-th prize if she buys $$$i$$$ tickets can be represented by $$$\frac{a_i}{b_i}$$$, where $$$a_i$$$ and $$$b_i$$$ are some integers.
The output will consist of $$$l$$$ lines. The $$$i$$$-th line will contain the unique integer $$$c_i$$$ satisfying $$$0 \le c_i \lt 998244353$$$ and $$$a_i \equiv b_i c_i \pmod{998244353}$$$.
3 1 1 41 2 3
855638017 748683265 332748118 199648871
