Construction of 5G Base Stations

题号：NC221777
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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   -- the length of the street and the number of base stations.

Each of the following  lines describes a base station with two integers  ,.

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

输出描述:

Print one integer -- the cost expectation modulo .

示例1

输入

复制

5 2
2 1
3 1

输出

复制

说明

In the first example, residents  and  connect to the first base station, and residents  and  connect to the second base station, so the running cost is .

示例2

输入

复制

2 2
1 499122177
2 499122177

输出

复制

554580199

说明

In the second example, the probability of successful connection with base stations  and  is , and the cost expectation is .