Problem11336--[yosupo] Enumerative Combinatorics - Number of Increasing Sequences Between Two Sequences

11336: [yosupo] Enumerative Combinatorics - Number of Increasing Sequences Between Two Sequences

[Creator : ]
Time Limit : 4.000 sec  Memory Limit : 512 MiB

Description

Given integers $N,M$ and two non-negative integer sequences $A = \left( A_0, A_1, \cdots, A_{N-1} \right), B = \left( B_0, B_1, \cdots, B_{N-1} \right)$.

Find the number of a non-negative integer sequences $x = \left( x_0, x_1, \cdots, x_{N-1} \right)$ which satisfies the following conditions, and print it $\bmod \ 998244353$.

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

Input

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

Constraints

- $1 \leq N \leq 2^{17}$
- $1 \leq M \leq 2^{17}$
- $0 \leq A_i < B_i \leq M$ ($0 \leq i \leq N - 1$)

Sample 1 Input

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

Sample 1 Output

48

Sample 2 Input

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

Sample 2 Output

0

Sample 3 Input

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

Sample 3 Output

13329431

HINT

Source/Category