P15900 [TOPC 2025] Chopsticks

Chisato works at a traditional Japanese restaurant that just received a shipment of beautifully handcrafted chopsticks. There are $m$ different types of chopsticks, and for each type $i$ ($1 \le i \le m$), there are exactly $k_i$ chopsticks. Tonight, $n$ guests have arrived, and each guest needs exactly one pair of chopsticks. Since no type of chopstick has at least $2n$ pieces, Chisato decides to randomly select $2n$ chopsticks from the full collection, which contains $s = \sum_{i=1}^{m} k_i$ chopsticks in total. After selecting the $2n$ chopsticks, Chisato will try to distribute them in a way that maximizes the number of guests receiving a matching pair, that is, two chopsticks of the same type. If it’s not possible to provide matching pairs for everyone, some guests will receive mismatched pairs. Your task is to compute the expected number of guests who receive mismatched pairs of chopsticks under this strategy.

The first line contains two integers $n$ and $m$, representing the number of people and the number of the chopstick type, respectively. The second line contains $m$ integers, the $i$-th integer $k_i$ represents the number of chopstick for the $i$-th type.

Print a single integer, the expected number of people who cannot get a pair of chopsticks of the same type, multiplied by $\binom{s}{2n}$ (where $s = \sum_{i=1}^{m} k_i$). It can be proven that this product is an integer. Output the result modulo $998244353$.

- $1 \le n \le 2.5 \times 10^5$ - $1 \le m \le 5 \times 10^5$ - $1 \le k_i < 2 \times n$ - $2 \times n \le s$