题目描述

長さ $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$ で割った余りを求めてください．

输入格式

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

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

输出格式

答えを出力せよ．

题目大意

给长度为 $N$ 和 $N-1$ 的正整数序列 $A$ 和 $B$，你可以进行以下操作任意次。

• 选择整数 $i$ 和 $j$($1\le i<j\le N$)，将 $A_i,A_j,B_i,B_{i+1}...B_{j-1}$ 减一。需要保证操作后不会出现负数。

令 $m$ 为可以执行的操作的次数的最大值，求出 $m$ 次操作后有多少种本质不同的序列 $A$（对 998244353 取模）。

• $1\le n\le 2\times 10^5$
• $1\le A_i\le 10^9$
• $1\le B_i\le 10^9$

输入格式：第一行输入一个正整数 $N$，第二、三行依次输入序列 $A$ 和 $B$。

输出格式：输出答案

3
1 2 2
1 2

3

4
1 1 1 1
2 2 2

1

4
2 2 3 4
3 1 4

3

提示

制約

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

Sample Explanation 1

$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)$ で操作すればよい．

Sample Explanation 2

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