← 返回题目列表

Codeforces · 1187/F

F. 期待的方美

中文机器翻译题面 查看原题

设 $$$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$$$;