Description

水果王國最近舉辦了一個營隊,其中一項(次要)目標就是把上次包鍋貼大賽的鍋貼吃掉。
到了午餐時間,有 $N$ 個人排成一列準備去拿鍋貼,已知活動主辦方事先指定好了排在第 $i$ 位的人可以拿 $A_i$ 個鍋貼。
但是人有時候會因為各種原因想吃更多的鍋貼或是更少的鍋貼,那麼為了讓每個人都可以拿到足夠的鍋貼,第 $i$ 個人的鍋貼數量,假設是 $X_i$,最多只能是前 $i-1$ 個人剩下的鍋貼數量 $+ A_i$,換句話說,對於所有的 $j$,$X_j \leq (\sum\limits_{i=1}^ {j-1} (A_i-X_i) )+ A_j$ 。
另外人有食量限制,主要是由以下的兩個數字 $B_i$ 跟 $C_i$ 定義,代表說 $X_i$ 要介在 $B_i$ 跟 $C_i$ 之間(含)才能吃飽又不至於吃得太撐。
現在活動主辦方很好奇,在這些限制下有多少種可能的 $X$ 序列滿足以上的條件。由於答案很大,請輸出答案 $\text{mod} \ 998244353$ 的餘數。
兩個序列 $X, Y$ 被視為不同若且唯若存在 $i$ 滿足 $X_i \neq Y_i$。

Input Format

第一行有一個整數 $N$,代表總共有幾個人。
第二行有 $N$ 個整數 $A_i$。
第三行有 $N$ 個整數 $B_i$。
第四行有 $N$ 個整數 $C_i$。

對於所有測試資料:

  • $1 \leq N \leq 2000$
  • $0\leq A_i\leq 5000$
  • $1 \leq \sum\limits^ n_{i=1} A_i \leq 5000$
  • $0 \leq B_i \leq C_i \leq 5000$

Output Format

輸出一個正整數,代表答案 $\text{mod} \ 998244353$ 的餘數

Sample Input 1

2
2 2
1 1
3 3

Sample Output 1

5

Sample Input 2

4
3 4 2 5
0 0 0 0
2000 2000 2000 2000

Sample Output 2

1333

Hints

範測一解釋:
$X = [1, 1], [1,2], [1, 3], [2, 1], [2, 2]$ 是符合條件的所有可能
$[3, 1]$ 不符合條件因為 $X_1 > A_1$
$[2, 0]$ 不符合條件因為 $X_2 < B_2$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~15 $N \leq 500$, $\sum\limits^ n_{i=1} A_i \leq 500$ 32
3 16~27 $B_i = 0$, $C_i = 5000$ 29
4 0~38 無額外限制 39

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 4
1 1000 262144 65536 1 2 4
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 2 4
15 1000 262144 65536 2 4
16 1000 262144 65536 3 4
17 1000 262144 65536 3 4
18 1000 262144 65536 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 4
29 1000 262144 65536 4
30 1000 262144 65536 4
31 1000 262144 65536 4
32 1000 262144 65536 4
33 1000 262144 65536 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4