设 $$$x$$$ 为整数数组 $$$x = [x_1, x_2, \dots, x_n]$$$。让我们将 $$$B(x)$$$ 定义为将 $$$x$$$ 划分为子段的最小大小,以便每个子段中的所有元素都相等。例如,$$$B([3, 3, 6, 1, 6, 6, 6]) = 4$$$ 使用下一个分区:$$$[3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]$$$。
现在你没有 $$$x$$$ 的任何精确值,但你知道 $$$x_i$$$ 可以是 $$$[l_i, r_i]$$$ ($$$l_i \le r_i$$$) 中统一随机的任何整数值。所有 $$$x_i$$$ 都是独立的。
计算 $$$(B(x))^2$$$ 或 $$$E((B(x))^2)$$$ 的预期值。保证期望值可以表示为有理分数 $$$\frac{P}{Q}$$$,其中 $$$(P, Q) = 1$$$,因此打印值 $$$P \cdot Q^{-1} \mod 10^9 + 7$$$。
输入
第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$x$$$ 的大小。
第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le 10^9$$$)。
第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$l_i \le r_i \le 10^9$$$)。
输出
打印单个整数 - $$$E((B(x))^2)$$$ 为 $$$P \cdot Q^{-1} \mod 10^9 + 7$$$。
示例
输入 #1
3 1 1 1 1 2 3
输出 #1
166666673
输入 #2
3 3 4 5 4 5 6
输出 #2
500000010
注意
让我们描述第一个样本的 $$$x$$$ 的所有可能值:
- $$$[1, 1, 1]$$$: $$$B(x) = 1$$$, $$$B^2(x) = 1$$$;
- $$$[1, 1, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 1, 3]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 1]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[1, 2, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 3]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
第二个样本的 $$$x$$$ 的所有可能值:
- $$$[3, 4, 5]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 4, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[3, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[4, 4, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 4, 6]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;