每个人都知道巴拉兹拥有全镇最漂亮的栅栏。它是由 $$$N$$$ 精美的部分组成的。这些部分是在地面上彼此紧密相邻的矩形。第 $$$i$$$ 部分具有整数高度 $$$h_i$$$ 和整数宽度 $$$w_i$$$。 我们正在这个精美的栅栏上寻找精美的矩形。 如果满足以下条件,则矩形很奇特:
- 它的边是水平的或垂直的并且具有整数长度
- 矩形与地面之间的距离是整数
- 矩形与第一部分左侧之间的距离为整数
- 它完全躺在部分上
输入
第一行包含 $$$N$$$ ($$$1\leq N \leq 10^{5}$$$) – 节数。 第二行包含 $$$N$$$ 以空格分隔的整数,第 $$$i$$$ 个数字是 $$$h_i$$$ ($$$1 \leq h_i \leq 10^{9}$$$)。 第三行包含$$$N$$$空格分隔的整数,第$$$i$$$个数字是$$$w_i$$$ ($$$1 \leq w_i \leq 10^{9}$$$)。
输出
你应该打印一个整数,即花式矩形的数量以 $$$10^9+7$$$ 为模。所以输出范围是$$$0,1,2,\ldots, 10^9+6$$$。
示例
输入 #1
2 1 2 1 2
输出 #1
12
注意
评分:
$$$ \begin{array}{|c|c|c|} \hline \text{子任务} & \text{点} & \text{约束} \\ \hline 1 & 0 & \text{样本}\\ \hline 2 & 12 & N \leq 50 \: \text{和} \: h_i \leq 50 \: \text{和} \: w_i = 1 \: \text{对于所有} \: i \\ \hline 3 & 13 & h_i = 1 \: \text{or} \: h_i = 2 \: \text{对于所有} \: i \\ \hline 4 & 15 & \text{所有} \: h_i \: \text{相等} \\ \hline 5 & 15 & h_i \leq h_{i+1} \: \text{对于所有} \: i \leq N-1 \\ \hline 6 & 18 & N \leq 1000\\ \hline 7 & 27 & \text{无附加约束}\\ \hline \end{数组} $$$
栅栏看起来像这样:
有 5 个奇特的矩形形状:
有 3 个奇特的矩形形状:
有 1 个奇特的矩形,其形状为:
有 2 个奇特的矩形形状:
有 1 个奇特的矩形,其形状为: