두 수열 사이의 증가 수열의 개수

정수 $N,M$와 두 음이 아닌 정수 수열 $A = \left( A_0, A_1, \cdots, A_{N-1} \right), B = \left( B_0, B_1, \cdots, B_{N-1} \right)$가 주어진다.

다음 조건을 만족하는 음이 아닌 정수 수열 $x = \left( x_0, x_1, \cdots, x_{N-1} \right)$의 개수를 구하고, 이를 $\bmod \ 998244353$ 출력한다.

• $0 \leq x_0 \leq \cdots \leq x_{N-1} < M$
• $A_i \leq x_i < B_i$

제한 조건

• $1 \leq N \leq 131072$
• $1 \leq M \leq 131072$
• $0 \leq A_i < B_i \leq M$ ($0 \leq i \leq N - 1$)

$N$ $M$
$A_0$ $A_1$ $\cdots$ $A_{N-1}$
$B_0$ $B_1$ $\cdots$ $B_{N-1}$

다음 조건을 만족하는 음이 아닌 정수 수열 $x = \left( x_0, x_1, \cdots, x_{N-1} \right)$의 개수를 구하고, 이를 $\bmod \ 998244353$ 출력한다.