CF1197E.Culture Code

There are famous Russian nesting dolls named matryoshkas sold in one of the souvenir stores nearby, and you'd like to buy several of them. The store has $n$ different matryoshkas. Any matryoshka is a figure of volume $out_i$ with an empty space inside of volume $in_i$ (of course, $out_i \gt in_i$).

You don't have much free space inside your bag, but, fortunately, you know that matryoshkas can be nested one inside another. Formally, let's call a set of matryoshkas nested if we can rearrange dolls in such a way, that the first doll can be nested inside the second one, the second doll — inside the third one and so on. Matryoshka $i$ can be nested inside matryoshka $j$ if $out_i \le in_j$. So only the last doll will take space inside your bag.

Let's call extra space of a nested set of dolls as a total volume of empty space inside this structure. Obviously, it's equal to $in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})$, where $i_1$, $i_2$, ..., $i_k$ are the indices of the chosen dolls in the order they are nested in each other.

Finally, let's call a nested subset of the given sequence as big enough if there isn't any doll from the sequence that can be added to the nested subset without breaking its nested property.

You want to buy many matryoshkas, so you should choose a big enough nested subset to buy it. But you will be disappointed if too much space in your bag will be wasted, so you want to choose a big enough subset so that its extra space is minimum possible among all big enough subsets. Now you wonder, how many different nested subsets meet these conditions (they are big enough, and there is no big enough subset such that its extra space is less than the extra space of the chosen subset). Two subsets are considered different if there exists at least one index $i$ such that one of the subsets contains the $i$-th doll, and another subset doesn't.

Since the answer can be large, print it modulo $10^9 + 7$.

附近的一家纪念品商店出售著名的俄罗斯套娃（matryoshkas），你想购买其中若干个。该商店共有 $n$ 种不同的套娃。每个套娃 $i$ 是一个体积为 $out_i$ 的实体，其内部有一个容积为 $in_i$ 的空腔（显然有 $out_i > in_i$）。

你的背包内部可用空间有限，但幸运的是，你知道套娃可以彼此嵌套。形式化地，我们称一组套娃是嵌套的（nested），如果能将它们重新排列，使得第一个套娃可以放入第二个套娃中，第二个套娃可以放入第三个套娃中，依此类推。套娃 $i$ 可以嵌入套娃 $j$ 中，当且仅当 $out_i \le in_j$。因此，在整个嵌套结构中，只有最外层的那个套娃会占用你背包内的空间。

我们定义一个嵌套套娃集合的额外空间（extra space）为该嵌套结构内部所有空腔体积的总和。显然，若所选套娃按嵌套顺序的下标为 $i_1, i_2, \dots, i_k$，则额外空间为

$$in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}}).$$

最后，我们称给定套娃序列的一个嵌套子集是足够大（big enough）的，如果无法再从原序列中加入任何一个剩余套娃，而不破坏该子集的嵌套性质。

你想购买尽可能多的套娃，因此应选择一个“足够大”的嵌套子集来购买。但若背包中浪费的空间过多，你会感到失望；因此，你希望在所有“足够大”的嵌套子集中，选出额外空间最小的那个。现在你想知道：有多少个不同的嵌套子集满足这些条件（即：它们是“足够大”的，且不存在另一个“足够大”的子集，其额外空间严格小于所选子集的额外空间）？若两个子集存在某个下标 $i$，使得其中一个包含第 $i$ 个套娃而另一个不包含，则认为这两个子集不同。

由于答案可能很大，请输出结果对 $10^9 + 7$ 取模的值。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of matryoshkas.

The next $n$ lines contain a description of each doll: two integers $out_i$ and $in_i$ ($1 \le in_i \lt out_i \le 10^9$) — the outer and inners volumes of the $i$-th matryoshka.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——套娃的数量。

接下来的 $n$ 行描述每个套娃：两个整数 $out_i$ 和 $in_i$（$1 \le in_i \lt out_i \le 10^9$）——第 $i$ 个套娃的外体积和内体积。

Print one integer — the number of big enough nested subsets such that extra space of each of these subsets is minimum possible. Since the answer can be large, print it modulo $10^9 + 7$.

输出一个整数——满足“足够大”的嵌套子集的个数，且这些子集的额外空间均取最小可能值。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。

There are $6$ big enough nested subsets with minimum possible extra space in the example:

• ${1, 5}$: we can't add any other matryoshka and keep it nested; it's extra space is $1$;
• ${1, 6}$;
• ${2, 4, 5}$;
• ${2, 4, 6}$;
• ${3, 4, 5}$;
• ${3, 4, 6}$.

There are no more "good" subsets because, for example, subset ${6, 7}$ is not big enough (we can add the $4$-th matryoshka to it) or subset ${4, 6, 7}$ has extra space equal to $2$.

示例中存在 $6$ 个足够大的嵌套子集，且它们的额外空间最小：

• ${1, 5}$：无法再添加任何其他套娃而保持其嵌套性；其额外空间为 $1$；
• ${1, 6}$；
• ${2, 4, 5}$；
• ${2, 4, 6}$；
• ${3, 4, 5}$；
• ${3, 4, 6}$。

不存在更多“好”的子集，例如，子集 ${6, 7}$ 不够大（我们可以向其中加入第 $4$ 个套娃），或子集 ${4, 6, 7}$ 的额外空间等于 $2$。