Background

Life has dreams, and everyone can be wonderful in their own way.

Problem Description

There are $n$ students taking an exam, and the exam has $m$ problems.

All students have the same ability, but the difficulty of each problem may be different. For the $i$-th problem, there will be a random $a_i$ students who answer it wrong.

After the exam, $k$ students are chosen uniformly at random. Find the probability that all of these students answered every problem correctly. Output the answer modulo $998244353$.

Input Format

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

The second line contains $m$ integers, where the $i$-th number represents $a_i$.

Output Format

Output one integer, the answer modulo $998244353$.

5 5 2
1 2 1 2 2

793364682

Hint

Sample Explanation

The probability that all randomly chosen $2$ students answer everything correctly is $\frac{243}{25000}$. Taking it modulo $998244353$, the answer is $793364682$.

It can be proven that the answer is always a rational number. If you are not familiar with taking a rational number modulo, you can refer to 【Template】Remainder of a Rational Number.

Constraints

• For $30\%$ of the testdata, $1 \le n, m \le 10$.
• For another $10\%$ of the testdata, $k = 0$.
• For another $20\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 10^5$.

For all testdata, it is guaranteed that $1 \le n, m \le 10^5$ and $0 \le k, a_i \le n$.

Translated by ChatGPT 5