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