AT_abc222_d.[ABC222D] Between Two Arrays

当且仅当对于所有 $i$ 满足 $1 \leq i \leq n-1$ 时都有 $s_i \leq s_{i+1}$，我们称长度为 $n$ 的数列 $S = (s_1, s_2, \dots, s_n)$ 是“广义单调递增”的。

给定两个长度为 $N$ 的广义单调递增整数列 $A = (a_1, a_2, \dots, a_N)$ 和 $B = (b_1, b_2, \dots, b_N)$。

请考虑满足以下条件的广义单调递增长度为 $N$ 的整数列 $C = (c_1, c_2, \dots, c_N)$：

• 对于所有 $i$ 满足 $1 \leq i \leq N$，都有 $a_i \leq c_i \leq b_i$。

请输出作为 $C$ 可能的数列的个数对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\dots$ $a_N$ $b_1$ $b_2$ $\dots$ $b_N$

输出作为 $C$ 可能的数列的个数对 $998244353$ 取模的结果。

限制条件

• $1 \leq N \leq 3000$
• $0 \leq a_i \leq b_i \leq 3000$（$1 \leq i \leq N$）
• 整数列 $A, B$ 均为广义单调递增。
• 输入均为整数。

样例解释 1

作为 $C$ 可能的数列有如下 $5$ 个：

• $(1, 1)$
• $(1, 2)$
• $(1, 3)$
• $(2, 2)$
• $(2, 3)$

注意，数列 $(2, 1)$ 不满足广义单调递增的条件，因此不计入答案。

样例解释 2

作为 $C$ 可能的数列仅有 $1$ 个：

• $(2, 2, 2)$

样例解释 3

请注意，要求输出的结果需对 $998244353$ 取模。

由 ChatGPT 4.1 翻译