Non-Intersecting Lattice Paths on an n×n Chessboard

Given an n × n chessboard with coordinates where the bottom‐left cell is (1,1) and the top‐right cell is (n,n), a piece at position (x,y) can move either one step to the right, to (x+1,y), or one step upward, to (x,y+1).

There are m pieces. The i^th piece starts at (a_i,1) and must reach (b_i,n). Determine the number of ways to move all pieces from their starting positions to their destinations such that the paths taken by any two pieces do not share any common cell. Two solutions are considered different if at least one piece visits a different set of cells along its path.

The answer should be output modulo 998244353.

Hint: For a single piece starting at $(a,1)$ and ending at $(b,n)$ (with $b\ge a$), the piece must make exactly $(b-a)$ right moves and $(n-1)$ up moves. Hence, the number of ways for such a piece is given by the binomial coefficient $$ \binom{(n-1)+(b-a)}{n-1} $$ A valid solution for all pieces exists only when, after sorting by the starting coordinate, the ending coordinates are in strictly increasing order. In addition to the product of the individual path counts, a correction factor (derived from the Lindstr\"om–Gessel–Viennot lemma) needs to be considered: $$ \prod_{1 \le i < j \le m} \frac{(b_j - b_i) - (a_j - a_i)}{j-i} $$ The final answer is the product of the individual counts multiplied by this correction factor, all computed modulo 998244353.

inputFormat

The first line contains two integers n and m $(1 \le n, m \le 10^5)$.

The second line contains m integers: a₁, a₂, …, a_m $(1 \le a_i \le n)$ which represent the starting x-coordinates of the pieces (the starting position of the i^th piece is (a_i,1)).

The third line contains m integers: b₁, b₂, …, b_m $(1 \le b_i \le n)$ which represent the destination x-coordinates (the destination of the i^th piece is (b_i,n)).

outputFormat

Output a single integer, the number of valid ways modulo 998244353.

sample

3 1
1
3

6