Expected Time to Collect k Distinct Ingredients

In order to open the door leading back to the mortal realm, Yopilla needs to forge a key. In the Lost Continent there are \(n\) types of raw materials available, and it is sufficient to collect any \(k\) of them to start the forging process.

Yopilla arrives at the core region of the continent. In each unit of time, one unit of raw material is generated randomly. The probability that the \(i\)-th raw material is generated is \(\frac{p_i}{m}\) (note that under the premise of the story, it is assumed that \(m=\sum_{i=1}^{n}p_i\) so that the total probability is 1). If Yopilla does not already have that raw material, he collects it.

Determine the expected number of time units (steps) until Yopilla has collected at least \(k\) distinct raw materials. Since the answer may be a rational number, output the answer modulo \(998244353\).

Note: All formulas must be presented in LaTeX format. For example, probabilities are given as \(\frac{p_i}{m}\) and the condition on the number of collected materials is \(\#\{\text{collected}\} \ge k\).

inputFormat

The first line contains three integers \(n\), \(k\) and \(m\) \( (1 \le k \le n,\; m = p_1+\cdots+p_n)\).

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\), where \(p_i\) represents the weight of the \(i\)-th raw material.

outputFormat

Output one integer: the expected time (in time units) to collect at least \(k\) distinct raw materials, taken modulo \(998244353\).

sample

2 2 2
1 1

3