Задача . E. Культурный код

В магазине неподалеку продаются известные русские деревянные игрушки под названием «матрешки», и вы бы хотели приобрести несколько штук. В магазине продается \(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\).