CF1197E Culture Code

在附近的一家纪念品商店里，有著名的俄罗斯套娃（matryoshka）出售，你想买几个。商店里有 $n$ 个不同的套娃。每个套娃的体积为 $out_i$，内部空间体积为 $in_i$（当然，$out_i > in_i$）。 你的包里空间不多，但幸运的是，你知道套娃可以相互嵌套。形式化地说，如果我们可以重新排列一组套娃，使得第一个套娃可以嵌套进第二个，第二个可以嵌套进第三个，依此类推，则称这组套娃是嵌套的。如果 $out_i \le in_j$，则套娃 $i$ 可以嵌套进套娃 $j$。因此，只有最外层的套娃会占用你包里的空间。 我们定义一组嵌套套娃的“额外空间”为该结构内部所有空余空间的总体积。显然，这等于 $in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})$，其中 $i_1, i_2, \ldots, i_k$ 是选中套娃按嵌套顺序的编号。 最后，我们称一个嵌套子集是“足够大”的，如果没有其它套娃可以加入该子集且不破坏其嵌套性质。 你想买尽可能多的套娃，所以你应该选择一个“足够大”的嵌套子集。但如果包里浪费太多空间你会失望，因此你希望选择一个“足够大”的子集，使其额外空间在所有“足够大”子集中最小。现在你想知道，有多少个不同的嵌套子集满足这些条件（即它们是“足够大”的，并且不存在额外空间更小的“足够大”子集）。如果存在至少一个编号 $i$，使得一个子集包含第 $i$ 个套娃而另一个不包含，则这两个子集被认为是不同的。 由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示套娃的数量。 接下来的 $n$ 行，每行包含两个整数 $out_i$ 和 $in_i$（$1 \le in_i < out_i \le 10^9$），分别表示第 $i$ 个套娃的外部体积和内部空间体积。

输出一个整数，表示所有“足够大”的嵌套子集中，额外空间最小的子集数量。由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。

在示例中，有 $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$。 由 ChatGPT 4.1 翻译