题目描述

長さ $n$ の数列 $S\ =\ (s_1,\ s_2,\ \dots,\ s_n)$ がすべての $i$ $(1\ \leq\ i\ \leq\ n\ -\ 1)$ に対して $s_i\ \leq\ s_{i+1}$ を満たすとき、かつそのときに限り「数列 $S$ は広義単調増加である」と呼びます。

広義単調増加な長さ $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$ で割ったあまりを出力せよ。

题目大意

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

$1\le n\le 3000$，$0\le a_i\le b_i\le 3000$。

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)$
• 整数列 $A,B$ は広義単調増加である。
• 入力はすべて整数である。

Sample Explanation 1

$C$ としてあり得る数列は次の $5$ 個です。 - $(1,\ 1)$ - $(1,\ 2)$ - $(1,\ 3)$ - $(2,\ 2)$ - $(2,\ 3)$ 数列 $(2,\ 1)$ は広義単調増加でないため条件を満たさないことに注意してください。

Sample Explanation 2

$C$ としてあり得る数列は次の $1$ 個です。 - $(2,\ 2,\ 2)$

Sample Explanation 3

個数を $998244353$ で割ったあまりを求めることに注意してください。