Exam Selection Probability

There are n students taking an exam consisting of m problems. All students have the same ability, but the problems may have different difficulties. For the i-th problem, exactly a_i students answer incorrectly; these a_i students are chosen uniformly at random out of the n students. After the exam, k students are selected uniformly at random. The task is to compute the probability that all of these k students answered every question correctly. Report the answer modulo $998244353$.

The probability for each problem can be expressed using combinatorics. For problem i, the probability that none of the chosen k students is among the a_i who answered incorrectly is

$$\frac{\binom{n-k}{a_i}}{\binom{n}{a_i}},$$

and, assuming independence across problems, the overall probability is

$$\prod_{i=1}^{m} \frac{\binom{n-k}{a_i}}{\binom{n}{a_i}} \pmod{998244353}. $$

If for any problem a_i exceeds n-k (i.e. if it is impossible for all k chosen students to have answered the problem correctly), then the answer is 0.

inputFormat

Input Format:
The first line contains three integers n, m, and k separated by spaces, where n is the number of students, m is the number of problems, and k is the number of selected students.
The second line contains m integers: a₁, a₂, ..., a_m, where each a_i is the number of students who answered the i-th problem incorrectly.

outputFormat

Output Format:
Output a single integer representing the probability that all k selected students answered all problems correctly, modulo $998244353$.

sample

5 3 2
1 2 1

?

</p>