「Radek and friends」社の社長であるRadekは、競合他社である「Mati and company」社の書類が置かれたすべての棚を水浸しにしようと企てました。完璧な妨害工作を行うため、彼は友人の配管工Januszに頼み、各棚の上に小さな蛇口を取り付けてもらいました。
「Mati and company」社の棚は、単純化のために平面上の線分として表現できます。各棚は、ある2点 $(l_i, h_i)$ と $(r_i, h_i)$ を結ぶ線分です。配管工が取り付けた蛇口は、座標 $(\frac{l_i+r_i}{2}, h_i + 0.5)$ にある点です。この部屋の床は $OX$ 軸として表現されます。
$i$ 番目の棚の上の蛇口が開けられた瞬間、その棚は水浸しになります。その自然な結果として、水は棚の端から垂直に流れ落ち、下の棚を水浸しにするか、あるいは自然な排水システムを備えた床へと流れ落ちます。
2番目のサンプルテストにおいて、1つの蛇口を開けた後の水の流れの可視化。
Radekは、ある決まった順序で蛇口を検討します。$i$ 番目の蛇口を検討する際、その時点で $i$ 番目の棚がまだ水浸しになっていない場合に限り、蛇口を開けます。
Radekはまだ蛇口を検討する順序を決めていません。彼は $n!$ 通りの順序から1つをランダムに選び、それぞれが等確率で選ばれるものとします。Radekは、平均して何個の蛇口を開ける必要があるかを知りたいと考えています。
あなたの課題は、Radekの問いに答え、その答えを $10^9 + 7$ を法として出力することです。形式的には、結果が $\frac{p}{q}$ （ただし $q \neq 0$ かつ $\gcd(p, q) = 1$）であるとき、$p \cdot q^{-1} \pmod{10^9 + 7}$ を出力してください。ここで $q^{-1}$ は $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$ を満たす集合 $\{1, 2, \dots, 10^9 + 6\}$ 内の唯一の数です。
問題の条件を満たすすべてのテストケースにおいて、結果は有理数であり、その既約分数形式の分母は $10^9 + 7$ で割り切れないことが証明できます。
入力
入力の1行目には、Mati社の棚の数を表す自然数 $n$ ($1 \le n \le 500\,000$) が与えられます。
続く $n$ 行には、棚の説明が与えられます。$i$ 番目の行には、問題文で説明された2つの自然数 $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$ までの数の順列を構成すると仮定して構いません。
出力
標準出力の1行目に、Radekが開ける必要のある蛇口の平均個数を $10^9 + 7$ を法として出力してください。
入出力例
入力 1
3 4 6 1 3 2 5
出力 1
2
入力 2
5 2 9 3 4 1 8 6 10 5 7
出力 2
233333338
注記
例の解説：最初のサンプルテストにおいて、Radekが蛇口を検討するすべての可能な順序を考えます。
- 順序 1, 2, 3 の場合、3つすべての蛇口を開けます。
- 順序 1, 3, 2 の場合、1番目と3番目の蛇口を開けます。3番目の蛇口を開けた後、水は2番目の棚も水浸しにするため、2番目の蛇口を開ける必要はありません。
- 順序 2, 1, 3 の場合、3つすべての蛇口を開けます。
- 順序 2, 3, 1 の場合、2番目と3番目の蛇口を開けます。3番目の蛇口を開けた後、水は1番目の棚を水浸しにするため、1番目の蛇口を開ける必要はありません。
- 順序 3, 1, 2 および 3, 2, 1 の場合、3番目の蛇口のみを開けます。これを開けた後、すべての棚が水浸しになるため、他の蛇口を開ける必要はありません。
したがって、Radekが開ける蛇口の平均個数は $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ 個です。
2番目のサンプルテストでは、Radekは平均して $\frac{91}{30}$ 個の蛇口を開ける必要があります。$30^{-1} \equiv 233333335 \pmod{10^9 + 7}$ であるため、$91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$ となります。