Глава компании «Radek i przyjaciele», Радек, решил затопить все полки с документами в конкурирующей фирме «Mati i spółka». Чтобы совершить идеальный саботаж, он попросил своего друга, сантехника Януша, установить небольшие краны с водой над каждой из полок.
Полки в фирме «Mati i spółka» для простоты можно представить в виде отрезков на плоскости. Каждая полка — это отрезок между парой точек $(l_i, h_i)$ и $(r_i, h_i)$. Краны, установленные сантехником, находятся в точках с координатами $(\frac{l_i+r_i}{2}, h_i + 0.5)$. Пол в этом помещении представлен осью $OX$.
В момент, когда кран над $i$-й полкой открывается, эта полка заливается водой. В результате вода начинает стекать вертикально вниз с краев полок, потенциально заливая нижележащие полки или стекая на пол, где расположена система водоотвода.
Визуализация стекающей воды после открытия одного крана во втором примере.
Радек будет рассматривать краны в некотором фиксированном порядке. В момент, когда он рассматривает $i$-й кран, он открывает его тогда и только тогда, когда $i$-я полка еще не залита.
Радек еще не определил порядок, в котором будет рассматривать краны. Он выберет случайным образом одну из $n!$ перестановок, каждую с равной вероятностью. Радек хотел бы узнать, сколько в среднем кранов ему придется открыть.
Ваша задача — ответить на вопрос Радека и предоставить ответ по модулю $10^9 + 7$. Формально, пусть результат равен $\frac{p}{q}$, где $q \neq 0$ и $\text{НОД}(p, q) = 1$. Тогда необходимо вывести число $p \cdot q^{-1} \pmod{10^9 + 7}$, где $q^{-1}$ — единственное число из множества $1, 2, \dots, 10^9 + 6$ такое, что $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$.
Можно доказать, что для всех тестов, удовлетворяющих условиям задачи, результат является рациональным числом, знаменатель которого в несократимом виде не делится на $10^9 + 7$.
Входные данные
В первой строке входных данных находится одно натуральное число $n$ ($1 \le n \le 500\,000$), определяющее количество полок в фирме «Mati i spółka».
В следующих $n$ строках находится описание полок. В $i$-й из этих строк находятся два натуральных числа $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$), описанные в условии задачи. Для простоты принимаем, что $h_i = i$.
Можно предположить, что все числа $l_i, r_i$ попарно различны — числа $l_i, r_i$ образуют перестановку чисел от $1$ до $2 \cdot n$.
Выходные данные
В единственной строке стандартного вывода должно находиться одно число, равное среднему количеству кранов, которые Радеку придется открыть, по модулю $10^9 + 7$.
Примеры
Пример 1
Входные данные:
3 4 6 1 3 2 5
Выходные данные:
2
Пример 2
Входные данные:
5 2 9 3 4 1 8 6 10 5 7
Выходные данные:
233333338
Примечание
Рассмотрим все возможные порядки, в которых Радек будет анализировать краны в первом примере: Для порядка 1, 2, 3 он откроет все 3 крана. Для порядка 1, 3, 2 он откроет первый и третий краны. После открытия третьего крана вода зальет также вторую полку, поэтому второй кран ему открывать не нужно. Для порядка 2, 1, 3 он откроет все 3 крана. Для порядка 2, 3, 1 он откроет второй и третий краны. После открытия третьего крана вода зальет первую полку, поэтому нет необходимости открывать первый кран. * Для порядков 3, 1, 2 и 3, 2, 1 он откроет только третий кран. После его открытия все полки будут залиты, поэтому нет необходимости открывать другие краны.
В среднем Радеку нужно открыть $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ крана.
Во втором примере Радеку в среднем нужно открыть $\frac{91}{30}$ кранов. Так как $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$, получаем $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$.