P4707 Return to the Real World

To open the gate back to the real world, Yopilla needs to craft the key that unlocks it. On the Lost Continent where Yopilla is, there are $n$ kinds of materials. As long as he gathers any $k$ kinds, he can start crafting. Yopilla arrives at the core area of the Lost Continent. In each unit of time, this area will randomly generate one kind of material. The probability of generating the $i$-th kind of material is $\frac{p_i}{m}$. If Yopilla does not have this material, then he can collect it. Yopilla urgently wants to know the expected time for him to collect any $k$ kinds of materials. Output the answer modulo $998244353$.

The first line contains three integers $n, k, m$. The second line contains $n$ integers $p_1, p_2, ..., p_n$.

Output one line.

For $10\%$ of the testdata, $p_1 = p_2 = ... = p_m$. For another $10\%$ of the testdata, $k = n$. For $70\%$ of the testdata, $n \le 100$. For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le k \le n$, $n - k \le 10$, $1 \le p_i \le m$, $\sum p = m$, $1 \le m \le 10000$。 Translated by ChatGPT 5