1219:套娃收纳

Description

locytus 有 \(n\) 个大小不一的套娃。每个套娃有一个内径 \(l_i\) 和一个外径 \(r_i\)，第 \(i\) 个套娃能嵌套到第 \(j\) 个套娃里当且仅当 \(r_i\le l_j\)，此外，每个套娃至多只能套住一个套娃。（被套住的套娃可以再套住另一个套娃）

套娃太多太占地方了，所以 locytus 决定把套娃尽可能套在一起，让所有套娃占的总空间最少。

具体来说，locytus 需要把序列 \(\{(l_1,r_1),\ldots,(l_n,r_n)\}\) 任意排序后，再划分成若干子序列 \(S_1,\ldots, S_m\)，使得每个序列形如 \(S_{j}=\{(l_{j,1},r_{j,1}),\ldots, (l_{j,|S_j|},r_{j,|S_{j}|})\}\) 满足 \(l_{j,t}\ge r_{j,t+1}\),\(t=1,2,\ldots,|S_{j}|-1\). 并且 \(\Sigma_{1\le j\le m} r_{j,1}^{3}\) 最小。

满足要求的套娃方案很多，locytus 想知道一共有多少种可能的方案。

方案数可能很大，只需要输出对 \(10^9+7\) 取模后的结果。

（注：两个方案 \(\{S_i\},\{T_i\}\)不同当且仅当存在有序集 \(S_i\) 与任意 \(T_j\) 均不相同，而诸如 \(\{S_1,S_2\}\) 和 \(\{S_2,S_1\}\) 这样的重排视为同一种方案）

Input

第一行包含一个正整数 \(n\) (\(1\le n \le 10^5\))，表示套娃总数。

接下来的 \(n\) 行，每行包含两个正整数 \(l_i,r_i(1\le l_i<r_i\le 2\times10^5)\)，表示每个套娃的内径和外径。数据保证不存在\(i\not=j\) 使得 \((l_i,r_i)=(l_j,r_j)\)。

Output

输出一个正整数，表示方案数对 \(10^9+7\) 取模的值。

Sample

Hint

样例的四种划分方案如下：

\(S_1=\{(4,5),(2,4),(1,2)\}, S_2=\{(3,4)\}\)

\(S_1=\{(4,5),(3,4),(1,2)\}, S_2=\{(2,4)\}\)

\(S_1=\{(4,5),(2,4)\}, S_2=\{(3,4),(1,2)\}\)

\(S_1=\{(4,5),(3,4)\}, S_2=\{(2,4),(1,2)\}\)

Source