H. Chopsticks
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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.

  • $$$1 \leq n \leq 2.5 \times 10^5$$$
  • $$$1 \leq m \leq 5 \times 10^5$$$
  • $$$1 \leq k_i \lt 2 \times n$$$
  • $$$2 \times n \leq s$$$
Output

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$$$.

Examples
Input
3 3
2 2 2
Output
0
Input
5 3
3 3 4
Output
1
Input
5 2
8 8
Output
4032