Problem Statement

There are N squares numbered 1 to N. Initially, all squares are painted white.
Additionally, there are M balls numbered 1 to M in a box.
We repeat the procedure below until all squares are painted black.

• Pick up a ball from a box uniformly at random.
• Let x be the index of the ball. Paint Squares $L_x, L_x+1, \ldots, R_x$ black.
• Return the ball to the box.

Find the expected value of the number of times the procedure is done, modulo 998244353 (see Notes).

Input

Input is given from Standard Input in the following format:
N M
L_1 R_1
L_2 R_2
$\hspace{0.5cm}\vdots$
L_M R_M

Output

Print the sought expected value modulo 998244353.

Constraints

• $1 \leq N,M \leq 400$
• $1 \leq L_i \leq R_i \leq N$
• For every square i, there is an integer j such that $L_j \leq i \leq R_j$.
• All values in input are integers.

Sample Input 1

3 3
1 1
1 2
2 3

Sample Output 1

499122180

The sought expected value is $\frac{7}{2}$.
We have $499122180 \times 2 \equiv 7\pmod{998244353}$, so 499122180 should be printed.

Sample Input 2

13 10
3 5
5 9
3 12
1 13
9 11
12 13
2 4
9 12
9 11
7 11

Sample Output 2

10

Sample Input 3

100 11
22 43
84 93
12 71
49 56
8 11
1 61
13 80
26 83
23 100
80 85
9 89

Sample Output 3

499122193

见题面 Input 部分

见题面 Output 部分