Description

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$.

Input Format

The first line contains three integers $n, k, m$.

The second line contains $n$ integers $p_1, p_2, ..., p_n$.

Output Format

Output one line.

3 3 3
1 1 1

499122182

Hint

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