题目描述

登山者高桥先生和青木先生最近穿越了一条著名的山脉。这个山脉由 $N$ 座山峰组成，从西向东呈直线排列，依次编号为 Mt. $1$, Mt. $2$, ..., Mt. $N$。高桥先生从西边开始穿越山脉，而青木先生则从东边开始。

第 $i$ 座山的高度为 $h_i$，但是他们忘记了每座山的具体高度。相反，对于每个 $i$ ($1 ≤ i ≤ N$)，他们记录了自己在到达第 $i$ 座山的过程中攀爬的山峰的最大高度（包括第 $i$ 座山）。高桥先生的记录是 $T_i$，青木先生的记录是 $A_i$。

已知每座山的高度 $h_i$ 都是正整数。请计算满足条件的可能山峰高度序列的数量，取模 $10^9 + 7$。

请注意，记录可能是错误的，因此可能没有满足条件的山峰高度序列。在这种情况下，请输出 $0$。

约束条件

• $1 ≤ N ≤ 10^5$
• $1 ≤ T_i ≤ 10^9$
• $1 ≤ A_i ≤ 10^9$
• $T_i ≤ T_{i+1}$ ($1 ≤ i ≤ N - 1$)
• $A_i ≥ A_{i+1}$ ($1 ≤ i ≤ N - 1$)

---

输入

从标准输入读入数据，输入格式如下：

$N$ $T_1$ $T_2$ $...$ $T_N$ $A_1$ $A_2$ $...$ $A_N$

输出

输出满足条件的可能山峰高度序列的数量，取模 $10^9 + 7$。

---

示例输入 1

5
1 3 3 3 3
3 3 2 2 2

示例输出 1

4

可能的山峰高度序列有：

• $1, 3, 2, 2, 2$
• $1, 3, 2, 1, 2$
• $1, 3, 1, 2, 2$
• $1, 3, 1, 1, 2$

共有四个序列。

---

示例输入 2

5
1 1 1 2 2
3 2 1 1 1

示例输出 2

0

记录存在矛盾，因为高桥先生在攀爬完所有山峰之后将 $2$ 记录为最高峰，而青木先生将 $3$ 记录为最高峰。

---

示例输入 3

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

示例输出 3

884111967

不要忘记取模 $10^9 + 7$。

---

示例输入 4

1
17
17

示例输出 4

1

有些山脉只有一座山。