Description

水果王國最近舉辦了一個營隊，其中一項（次要）目標就是把上次包鍋貼大賽的鍋貼吃掉。
到了午餐時間，有 $N$ 個人排成一列準備去拿鍋貼，已知活動主辦方事先指定好了排在第 $i$ 位的人可以拿 $A_{i}$ 個鍋貼。
但是人有時候會因為各種原因想吃更多的鍋貼或是更少的鍋貼，那麼為了讓每個人都可以拿到足夠的鍋貼，第 $i$ 個人的鍋貼數量，假設是 $X_{i}$ ，最多只能是前 $i - 1$ 個人剩下的鍋貼數量 $+ A_{i}$ ，換句話說，對於所有的 $j$ ， $X_{j} \leq (\sum_{i = 1}^{j - 1} (A_{i} - X_{i})) + A_{j}$ 。
另外人有食量限制，主要是由以下的兩個數字 $B_{i}$ 跟 $C_{i}$ 定義，代表說 $X_{i}$ 要介在 $B_{i}$ 跟 $C_{i}$ 之間（含）才能吃飽又不至於吃得太撐。
現在活動主辦方很好奇，在這些限制下有多少種可能的 $X$ 序列滿足以上的條件。由於答案很大，請輸出答案 $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_{i = 1}^{n} A_{i} \leq 5000$
$0 \leq B_{i} \leq C_{i} \leq 5000$

Output Format

輸出一個正整數，代表答案 $mod 998244353$ 的餘數

Sample Input 1

Sample Output 1

Sample Input 2

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

Sample Output 2

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_{i = 1}^{n} 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

Submit out of contest

2322 . 拿鍋貼