問題文

長さ $N$ の正整数列 $A$ 及び長さ $N-1$ の正整数列 $B$ が与えられます． あなたは，次の操作を好きな回数行うことができます．

• 整数 $i,j$ ($1 \\leq i < j \\leq N$) を選び，$A_i,A_j,B_i,B_{i+1},\\cdots,B_{j-1}$ の値をそれぞれ $1$ 減らす． ただし，操作後に負になる値が存在してはならない．

ここで，操作を行える回数の最大値を $m$ とおきます． $m$ 回の操作後の $A$ としてありえる数列が何通りあるかを $998244353$ で割った余りを求めてください．

制約

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i \\leq 10^9$
• $1 \\leq B_i \\leq 10^9$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $A_1$ $A_2$ $\\cdots$ $A_N$ $B_1$ $B_2$ $\\cdots$ $B_{N-1}$

出力

答えを出力せよ．

入力例 1

3
1 2 2
1 2

出力例 1

3

$m=2$ であり，最終的な $A$ としては以下の $3$ 通りが考えられます．

• $A=(1,0,0)$: $(i,j)=(2,3)$ と $(i,j)=(2,3)$ で操作すればよい．
• $A=(0,1,0)$: $(i,j)=(1,3)$ と $(i,j)=(2,3)$ で操作すればよい．
• $A=(0,0,1)$: $(i,j)=(1,2)$ と $(i,j)=(2,3)$ で操作すればよい．

入力例 2

4
1 1 1 1
2 2 2

出力例 2

1

$B$ の値が異なっていても $A$ の値が同じなら区別しないことに注意してください．

入力例 3

4
2 2 3 4
3 1 4

出力例 3

3