题目描述

给定两个单调不下降的序列 $a$，$b$，单调不下降的序列意思是对于任意一个 $1\leq i\leq n-1$ 的 $i$，满足 $a_i\leq a_{i+1}$ 。

求长度为 $n$ 的单调不下降序列 $c$ 的数量，其中每个元素还需要满足 $a_i\le c_i\le b_i$。对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$

接下来一行 $n$ 个整数代表 $a_1,a_2,\cdots,a_n$

接下来一行 $n$ 个整数代表 $b_1,b_2,\cdots,b_n$

输出格式

输出满足条件的序列 $c$ 的个数。

2
1 1
2 3

5

3
2 2 2
2 2 2

1

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

978222082

提示

• $1\ \leq\ N\ \leq\ 3000$
• $0\ \leq\ a_i\ \leq\ b_i\ \leq\ 3000$ $(1\ \leq\ i\ \leq\ N)$

样例解释 1

样例 $1$ 有 $5$ 个满足要求的序列 $c$ 分别如下：

• 1, 1
• 1, 2
• 1, 3
• 2, 2
• 2, 3