题目描述

给定两个长度为 $N$ 单调不下降的序列 $a$，$b$，求单调不下降序列 $c$ ，满足 $a_i \le c_i \le b_i$ 并且最长，问这样的 $c$ 的数量。对 $998244353$ 取模。

输入格式

输入格式如下：

$N$

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

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

输出格式

输出可能的序列 $C$ 的数量，对 $998244353$ 取模后的结果。

输入输出样例

样例1输入：

2
1 1
2 3

样例1输出：

5

说明：符合条件的序列有$(1,1)$、$(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$共5种。注意$(2,1)$不满足单调递增条件。

样例2输入：

3
2 2 2
2 2 2

样例2输出：

1

说明：唯一符合条件的序列是$(2,2,2)$。

样例3输入：

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

样例3输出：

978222082

数据范围

• $1 \leq N \leq 3000$
• $0 \leq a_i \leq b_i \leq 3000$
• 序列 $A$ 和 $B$ 保证单调不下降
• 所有输入均为整数