Contest Duration: - (local time) (100 minutes) Back to Home
D - Between Two Arrays /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

このとき、次の条件を満たす広義単調増加な長さ N の整数列 C = (c_1, c_2, \dots, c_N) を考えます。

• すべての i (1 \leq i \leq N) に対して a_i \leq c_i \leq b_i が成り立つ。

### 制約

• 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 で割ったあまりを出力せよ。

### 入力例 1

2
1 1
2 3


### 出力例 1

5


C としてあり得る数列は次の 5 個です。

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

### 入力例 2

3
2 2 2
2 2 2


### 出力例 2

1


C としてあり得る数列は次の 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


Score : 400 points

### Problem Statement

A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).

Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:

• a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).

Find the number, modulo 998244353, of sequences that can be C.

### Constraints

• 1 \leq N \leq 3000
• 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
• The sequences A and B are non-decreasing.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \dots a_N
b_1 b_2 \dots b_N


### Output

Print the number, modulo 998244353, of sequences that can be C.

### Sample Input 1

2
1 1
2 3


### Sample Output 1

5


There are five sequences that can be C, as follows.

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

Note that (2, 1) does not satisfy the condition since it is not non-decreasing.

### Sample Input 2

3
2 2 2
2 2 2


### Sample Output 2

1


There is one sequence that can be C, as follows.

• (2, 2, 2)

### Sample Input 3

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


### Sample Output 3

978222082


Be sure to find the count modulo 998244353.