附近的一家纪念品商店里有卖俄罗斯著名的套娃,名为“套娃”,您想买几个。这家商店有$$$n$$$不同的俄罗斯套娃。任何俄罗斯套娃都是一个卷 $$$out_i$$$ 的图形,卷 $$$in_i$$$ 内部有一个空白空间(当然,$$$out_i > in_i$$$)。
您的包内没有太多可用空间,但幸运的是,您知道俄罗斯套娃可以嵌套在一起。正式地,如果我们能够以这样的方式重新排列娃娃,即第一个娃娃可以嵌套在第二个娃娃内,第二个娃娃可以嵌套在第三个娃娃内,依此类推,那么我们可以将一组套娃称为嵌套的。俄罗斯套娃 $$$i$$$ 可以嵌套在俄罗斯套娃 $$$j$$$ 中,前提是 $$$out_i \le in_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$$$, ..., $$$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$$$ 取模。
示例
输入 #1
7 4 1 4 2 4 2 2 1 5 4 6 4 3 2
输出 #1
6
注意
示例中有 $$$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$$$ 的额外空间。