Пусть $$$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$$$.
3 1 1 1 1 2 3
166666673
3 3 4 5 4 5 6
500000010
Опишем все возможные значения массива $$$x$$$ из первого примера:
Все возможные значения $$$x$$$ из второго примера:
Название |
---|