F. Ожидаемый квадрат красоты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$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$$$ из первого примера:

  • $$$[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$$$;
В результате $$$E = \frac{1}{6} (1 + 4 + 4 + 9 + 4 + 9) = \frac{31}{6}$$$ или $$$31 \cdot 6^{-1} = 166666673$$$.

Все возможные значения $$$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$$$;
В результате $$$E = \frac{1}{8} (9 + 9 + 4 + 9 + 4 + 4 + 4 + 9) = \frac{52}{8}$$$ или $$$13 \cdot 2^{-1} = 500000010$$$.