問題文

整数列 L = (L_1, L_2, \dots, L_N) と R = (R_1, R_2, \dots, R_N) が与えられます。 以下の条件を満たす整数列 A = (A_1, A_2, \dots, A_N) の個数を 998244353 で割ったあまりを求めてください。

• 1 \leq i \leq N を満たすすべての整数 i に対して L_i \leq A_i \leq R_i が成り立つ。
• ある整数 d が存在して、1 \leq i \leq N-1 を満たすすべての整数 i に対して A_{i+1} - A_i = d が成り立つ。

制約

• 入力はすべて整数
• 2 \leq N \leq 3 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^{12} (1 \le i \le N)

部分点

以下の条件を満たすデータセットに正解した場合は 100 点が与えられる。

• 1 \leq L_i \leq R_i \leq 10^5 (1 \le i \le N)

入力例 1

3
5 5 2
7 6 7

出力例 1

6

例えば A = (7, 5, 3) が条件を満たします。

入力例 2

4
2 3 1 6
5 6 4 8

出力例 2

0