D - 两个数组之间

得分：$400$分

题目描述

一个包含$n$个数字的序列$S=(s_1, s_2, \dots, s_n)$，如果对于每个$i$ $(1 \leq i \leq n - 1)$都有$s_i \leq s_{i+1}$，那么称其为非递减序列。

给定两个非递减序列$A=(a_1, a_2, \dots, a_N)$和$B=(b_1, b_2, \dots, b_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$取模。

约束条件

• $1 \leq N \leq 3000$
• $0 \leq a_i \leq b_i \leq 3000$ $(1 \leq i \leq N)$
• 给定的$A$和$B$是非递减序列。
• 输入的所有值都是整数。

输入

从标准输入中按以下格式给出输入：

$N$

$a_1$ $a_2$ $\dots$ $a_N$

$b_1$ $b_2$ $\dots$ $b_N$

输出

输出满足条件的序列$C$的数量，对$998244353$取模。

2
1 1
2 3

5

满足条件的序列$C$有五个，如下所示：

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

注意，$(2, 1)$不满足条件，因为它不是非递减序列。

3
2 2 2
2 2 2

1

满足条件的序列$C$有一个，如下所示：

• $(2, 2, 2)$

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

978222082

确保对$998244353$取模。