408442: GYM103118 L Construction of 5G Base Stations

Construction of 5G base stations is underway on Piggy street. However, the service provider has run into some trouble, and he needs your help.

Piggy street can be abstracted as number axes. There are $$$n$$$ residents living on integer points $$$1, 2, 3, 4, \dots, n$$$. There are also $$$m$$$ $$$(1 \le m \le n)$$$ 5G base stations located on the integer points of $$$1, 2, 3, 4, \dots, n$$$, and there will not be two base stations located at the same location.

Every resident likes to solve programming problems on the network, so they need to establish a network connection with the base station. The probability of successful connection with a base station located at $$$x_i$$$ is $$$p_i$$$ $$$(1 \le i \le m)$$$.

The residents will try to connect to the base station from near to distant, and if the connection fails, the next one will be tried. If all the base stations have been tried, the cycle will be repeated – i.e., starting from the nearest base station until a connection is established. If there are two base stations at the same distance, the base station located to the left of the resident is preferred.

These base stations adopt an outdated and inefficient switching model. It connects two residents to communicate with each other through a physical line, which results in very high running costs. To be straightforward, suppose the number of residents connected to a particular base station is $$$x$$$, the running cost of that base station is $$$x^2$$$.

For the service provider, the cost of Piggy street is the sum of all the base station running costs. Now he asks you to tell him the cost expectation for Piggy street.

To avoid accuracy errors, it is guaranteed that the cost expectation can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not \equiv 0 (\bmod 998244353)$$$. Print the value of $$$P \cdot Q^{-1} \bmod 998244353$$$. Note that $$$p_1, p_2, \dots, p_m$$$ are also given in the same form.

The first line contains two positive integers $$$n, m$$$ $$$(1 \le m \le n \le 10^6)$$$ – the length of the street and the number of base stations.

Each of the following $$$m$$$ lines describes a base station with two integers $$$x_i, p_i$$$ ($$$1 \le x_i \le n$$$, $$$0 < p_i < 998244353$$$).

It is guaranteed that the probability that a resident fails to connect all the stations is not $$$1$$$ modulo $$$998244353$$$.

Print one integer – the cost expectation modulo $$$998244353$$$.

5 2
2 1
3 1

13

2 2
1 499122177
2 499122177

554580199

In the first example, residents $$$1$$$ and $$$2$$$ connect to the first base station, and residents $$$3,4$$$ and $$$5$$$ connect to the second base station, so the running cost is $$$2^2 + 3^2 = 13$$$.

In the second example, the probability of successful connection with base stations $$$1$$$ and $$$2$$$ is $$$\frac{1}{2}$$$, and the cost expectation is $$$\frac{26}{9}$$$.