问题陈述

一个序列 $S = (s_1, s_2, \ldots, s_n)$ 如果且仅如果对于每个 $i$ $(1 \leq i \leq n-1)$ 都满足 $s_i \leq s_{i+1}$，那么它被称作 不递减 序列。

给定的是每个都是不递减的整数序列：$A = (a_1, a_2, \ldots, a_N)$ 和 $B = (b_1, b_2, \ldots, b_N)$。
考虑一个满足以下条件的不递减整数序列：$C = (c_1, c_2, \ldots, 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$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_N$

输出

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

示例输入 1

2
1 1
2 3

示例输出 1

5

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

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

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

示例输入 2

3
2 2 2
2 2 2

示例输出 2

1

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

• $(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

确保对 $998244353$ 取模之后获得结果。