408217: GYM103055 K Grammy's Kingdom

Grammy's kingdom is in danger. Some foreign invaders have intruded into her kingdom and they are destroying the traffic system. There are $$$n$$$ stations indexed from $$$1$$$ to $$$n$$$ in the traffic system. Moreover, there are $$$m$$$ ($$$m\leq n$$$) airports located in some of the stations. If you are in station $$$i$$$, you can transfer to station $$$i+1$$$ if $$$i$$$ and $$$i+1$$$ haven't been destroyed. If you are in station $$$i$$$ with an airport, you can fly to station $$$j$$$ if $$$i\leq j$$$ and station $$$j$$$ has an airport and both of the stations haven't been destroyed. We define the stability $$$G$$$ of the system as the number of routes that still available.

Formally, $$$G=\sum_{1\leq i\leq j\leq n}$$$[a person in station $$$i$$$ can transfer to station $$$j$$$ via several stations or airports].

At each moment $$$i$$$ ($$$1\leq i\leq n$$$), the invaders will randomly choose an undestroyed station $$$x$$$ and destroy it as well as the airport in it (If there exists an airport in it).

We define $$$E(x)$$$ as the expected value of $$$x$$$. Grammy wonders the value of $$$\sum_{i=1}^n E(G_i)$$$ modulo $$$998\,244\,353$$$. Could you please help her? Here, $$$G_i$$$ denotes the value of the stability $$$G$$$ after the invaders destroying the $$$i$$$-th chosen station at the $$$i$$$-th moment.

The input contains only a single case.

The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 2\,000\,000$$$, $$$0\leq m\leq n$$$), denoting the number of stations and the number of airports.

The second line contains $$$m$$$ distinct integers $$$x_1, x_2, \dots, x_m$$$ ($$$1\leq x_i\leq n$$$), denoting the indexes of station that has an airport.

Output one integer, the value of $$$\sum_{i=1}^n E(G_i)$$$ modulo $$$998\,244\,353$$$.

1 0

0

3 3
1 2 3

4

6 2
2 4

16637434

It can be proved that the answer can be represented as a rational number $$$\dfrac pq$$$ with $$$\gcd(p,q)=1$$$. Therefore, you are asked to find the value of $$$pq^{-1} \bmod 998\,244\,353$$$. It can be shown that $$$q \bmod 998\,244\,353\neq 0$$$ under the given constraints of the problem.