Culture Code

题意翻译

有一些俄罗斯套娃，第 $i$ 个套娃从外部看体积为 $out_i$，内部空心体积为 $in_i$，显然 $in_i<out_i$ 你想把一些套娃放进包里，幸运的是你可以把它们套起来带走，具体地，若 $out_i\le in_j$，你可以把套娃 $i$ 套在套娃 $j$ 里面。 现在你套了一些套娃，设这些套娃编号为 $i_1, i_2, \cdots, i_k$，则剩余空间为 $in_{i_1}+(in_{i_2}-out_{i_1})+\cdots+(in_{i_k}-out_{i_k-1})$。你套的套娃序列中如果能够加入更多套娃，则不合法 记所有方案中剩余空间的最小值为 $m$，你需要输出剩余空间等于 $m$ 的方案的个数，因为 Aiming_High 太强了，所以答案对 $10^9+7$ 取模。

题目描述

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 > 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 $ .

输入输出格式

输入格式

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 < out_i \le 10^9 $ ) — the outer and inners volumes of the $ i $ -th matryoshka.

输出格式

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 $ .

输入输出样例

输入样例 #1

7
4 1
4 2
4 2
2 1
5 4
6 4
3 2

输出样例 #1

6

说明

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 $ .

题意翻译

有一些俄罗斯套娃，第 $i$ 个套娃从外部看体积为 $out_i$，内部空心体积为 $in_i$，显然 $in_i<out_i$ 你想把一些套娃放进包里，幸运的是你可以把它们套起来带走，具体地，若 $out_i\le in_j$，你可以把套娃 $i$ 套在套娃 $j$ 里面。 现在你套了一些套娃，设这些套娃编号为 $i_1, i_2, \cdots, i_k$，则剩余空间为 $in_{i_1}+(in_{i_2}-out_{i_1})+\cdots+(in_{i_k}-out_{i_k-1})$。你套的套娃序列中如果能够加入更多套娃，则不合法 记所有方案中剩余空间的最小值为 $m$，你需要输出剩余空间等于 $m$ 的方案的个数，因为 Aiming_High 太强了，所以答案对 $10^9+7$ 取模。