两序列间递增序列个数

【题目描述】

给定整数 $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)$ 的个数，并将其对 $998244353$ 取模后输出。

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

【输入】

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

【输出】

输出满足条件的序列 $x$ 的个数对 $998244353$ 取模的结果。

【输入样例】

5 9
0 0 3 2 5
8 3 4 5 9

【输出样例】

48

【输入样例2】

5 9
0 0 5 2 0
8 3 9 5 9

【输出样例2】

0

【输入样例3】

12 100
7 10 12 17 18 20 27 36 41 52 52 62
48 50 52 67 68 71 100 100 100 100 100 100

【输出样例3】

13329431

【数据范围】

• $1 \leq N \leq 131072$
• $1 \leq M \leq 131072$
• $0 \leq A_i < B_i \leq M$（$0 \leq i \leq N - 1$）

【来源】

Library Checker（yosupo06） number_of_increasing_sequences_between_two_sequences