给定两个整数序列 $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 \le i \le N$ 的整数 $i$，都有 $L_i \le A_i \le R_i$。
• 令 $d = A_2 - A_1$。对于所有满足 $1 \le i \le N - 1$ 的整数 $i$，都有 $A_{i+1} - A_i = d$。

输入格式

输入通过标准输入按以下格式给出：

$N$ $L_1 \ L_2 \ \dots \ L_N$ $R_1 \ R_2 \ \dots \ R_N$

• 输入中的所有值均为整数。
• $2 \le N \le 3 \times 10^5$
• $1 \le L_i \le R_i \le 10^{12} \ (1 \le i \le N)$

输出格式

输出满足条件的序列 $A$ 的数量，对 $998244353$ 取模。

样例

样例输入 1

3
5 5 2
7 6 7

样例输出 1

6

样例输入 2

4
2 3 1 6
5 6 4 8

样例输出 2

0

说明

在第一个样例中，共有 6 个满足条件的序列：$(5, 5, 5), (5, 6, 7), (6, 5, 4), (6, 6, 6), (7, 5, 3), (7, 6, 5)$。