Problem Description

Motsu-P, the producer of an idol group consisting of $ N $ members, has decided to form a unit within the group with $ K $ members. In order to select members with good luck, the $ K $ unit members will be chosen uniformly at random just before the live performance.

Each idol $i\ (1\leq\ i\leq\ N)$ possesses $ M_i $ costumes numbered $1,\ 2,\ldots,M_i$. They were told that they could wear any of their costumes for the new unit debut live, so they will each choose one uniformly at random from their collection. However, Motsu-P has realized that it would be better if the unit costumes matched. Unfortunately, it is already the day of the live performance, and there is no time to change the costumes now. Please calculate the probability that the unit costumes accidentally match for the sake of Motsu-P's mental stability.

A unit's costumes are considered to match if and only if all members' costume numbers are the same. Since the probability to be calculated is provably a rational number, output it modulo $ 998244353 $ as described in the notes.

Output Method When outputting a rational number, first represent it as a fraction $\frac\ p\ q$ where $p,\ q$ are integers and $ q $ is not divisible by $ 998244353 $ (under the constraints of this problem, such a representation is always possible). Then, output the unique integer $ r $ such that $0 \leq r < 998244353$ and $p\equiv\ qr\pmod{998244353}$.

Unit Member and Costume Selection Method Both the unit members and each idol's chosen costume are selected independently and uniformly at random. That is, the unit members are chosen from ${}_N\ C_K$ possible combinations with equal probability. Independently, each idol $ i $ chooses a costume from $ M_i $ possibilities with equal probability.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ M_1 $ $ M_2 $ $\ldots$ $ M_N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

3 2
1 2 3

Sample Output #1

55458020

Sample Input #2

10 5
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751

Sample Output #2

819006280

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ K\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M_i\ \leq\ 10^8\ (1\leq\ i\leq\ N)$

Partial Points

• Correctly solving the dataset where $1\ \leq\ N\ \leq\ 2000$ will award $ 50 $ points.

Sample Explanation 1

Representing the chosen idols as $ (x,y) $, the probability that the unit costumes match is $\frac12$ for $ (1,2) $, $\frac13$ for $ (1,3) $, and $\frac13$ for $ (2,3) $. Overall, this results in $\frac13\left(\frac12+\frac13+\frac13\right)=\frac7{18}$. Remember to output the answer modulo $ 998244353 $.

见题面 Input 部分

见题面 Output 部分