大家都知道 Balázs 拥有全镇最精美的栅栏。它由 $N$ 个精美的部分组成。这些部分是紧挨着立在地面上的矩形。第 $i$ 个部分的整数高度为 $h_i$，整数宽度为 $w_i$。
我们正在寻找这个精美栅栏上的“精美矩形”。一个矩形是精美的，当且仅当：
- 它的边是水平或垂直的，且长度为整数
- 矩形与地面之间的距离为整数
- 矩形与第一部分左侧之间的距离为整数
- 它完全位于栅栏的部分之内
精美矩形的数量是多少？ 这个数字可能非常大，因此我们对它模 $10^9 + 7$ 的结果感兴趣。
输入格式
第一行包含一个整数 $N$，表示部分的数量。 第二行包含 $N$ 个空格分隔的整数，第 $i$ 个数为 $h_i$。 第三行包含 $N$ 个空格分隔的整数，第 $i$ 个数为 $w_i$。
输出格式
输出一个整数，即精美矩形的数量模 $10^9 + 7$ 的结果。因此输出范围为 $0, 1, 2, \dots, 10^9 + 6$。
样例
样例输入 1
2 1 2 1 2
样例输出 1
12
说明
有 5 个这种形状的精美矩形：
有 3 个这种形状的精美矩形：
有 1 个这种形状的精美矩形：
有 2 个这种形状的精美矩形：
有 1 个这种形状的精美矩形：
数据范围
$1 \le N \le 10^5$ $1 \le h_i, w_i \le 10^9$
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 0 | 样例 |
| 2 | 12 | $N \le 50$ 且 $h_i \le 50$ 且对于所有 $i$，$w_i = 1$ |
| 3 | 13 | 对于所有 $i$，$h_i = 1$ 或 $h_i = 2$ |
| 4 | 15 | 所有 $h_i$ 相等 |
| 5 | 15 | 对于所有 $i \le N - 1$，$h_i \le h_{i+1}$ |
| 6 | 18 | $N \le 1000$ |
| 7 | 27 | 无附加限制 |