P10365 [PA 2024] Kraniki

PA 2024 5B2

**This problem is translated from [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Round 5 [Kraniki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/kra/).** Radek, the boss of *Radek and Friends*, is trying to flood all shelves of the competing company *Mati and Company*. To carry out the perfect sabotage, he asked his friend, the plumber Janusz, to install a small faucet above each shelf. For simplicity, the shelves in *Mati and Company* can be represented as line segments on the plane. Each shelf is the segment between the points $(l_i, h_i)$ and $(r_i, h_i)$. The faucet installed by the plumber is the point with coordinates $(\frac{l_i+r_i}{2}, h_i + 0.5)$. The floor of the room is represented by the $OX$ axis. As soon as the faucet above shelf $i$ is opened, that shelf will be flooded. Then the water will naturally start dripping vertically downward from both ends of the shelf, and it may flood more shelves, or drip down to the floor.  In the second sample, a visualization of the water flow after opening one faucet. Radek will inspect the faucets in some fixed order. When he sees faucet $i$, he will open it if and only if shelf $i$ has not been flooded yet. Radek has not decided the order in which he will inspect the faucets. He will choose one uniformly at random among the $n!$ possible orders. Radek wants to know the expected number of faucets he will open. Your task is to answer Radek’s question and output the value modulo $10^9+7$. Formally, let the answer be $\frac{p}{q}$, where $q\neq 0$ and $\gcd(p,q)=1$. You need to output $p\cdot q^{-1}\pmod{10^9+7}$, where $q^{-1}$ is the unique integer in the set $1,2,\ldots,10^9+6$ such that $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$. It can be proven that for all testdata satisfying the constraints of the problem, the result is a rational number, and its denominator is not divisible by $10^9+7$.

The first line contains an integer $n\ (1\le n\le 500\,000)$, the number of shelves in Mati’s company. The next $n$ lines each contain two integers $l_i,r_i\ (1\le l_i

Output one integer: the expected number of faucets Radek needs to open, taken modulo $10^9+7$.

**Sample Explanation 1** Let us consider all orders in which Radek may inspect the faucets in the first sample: - In the order $1,2,3$, he will open all $3$ faucets. - In the order $1,3,2$, he will first open faucets $1$ and $3$. When he is about to open faucet $2$, shelf $2$ has already been flooded, so he does not need to open faucet $2$. - In the order $2,1,3$, he will open all $3$ faucets. - In the order $2,3,1$, he will first open faucets $2$ and $3$. When he is about to open faucet $1$, shelf $1$ has already been flooded, so he does not need to open faucet $1$. - In the order $3,1,2$ or $3,2,1$, after opening faucet $3$, all shelves will be flooded, so there is no need to open the remaining two faucets. Radek needs to open $\frac{1}{6}\cdot(3+2+3+2+1+1)=2$ faucets on average. **Sample Explanation 2** In the second sample, Radek needs to open $\frac{91}{30}$ faucets on average. Since $30^{-1}\equiv 233333335\pmod{10^9+7}$, the output is $91\cdot 233333335\equiv 21233333485\equiv 233333338\pmod{10^9+7}$. Translated by ChatGPT 5