Задача №115276. Одномерная игра
Богдан играет в игру. Игра одномерная — в ней есть \(n\) платформ, расположенных на одной горизонательной прямой. Между платформами можно перемещаться. \(i\)-я платформа это горизонтальный отрезок на прямой \([l_i, r_i]\). Все отрезки различны.
Будем говорить, что платформа \(j\) вложена в платформу \(i\), если \(l_i \le l_j\) и \(r_j \le r_i\).
В начале игры Богдан выбирает платформу с которой он начнёт свой путь. Прыжки между платформами — занятие опасное, а Богдан старается держаться далеко от опасности, поэтому с платформы \(i\) он может прыгнуть на платформу \(j\), только если платформа \(j\) вложена в платформу \(i\), а также не существует другой платформы \(k\), вложенной в платформу \(i\), в которую вложена платформа \(j\).
Для каждой платформы Богдану интересно сколько различных маршрутов он сможет пройти, начав с этой платформы и закончив на любой другой. Два маршрута считаются различными, если существует платформа, которая есть в одном маршруте, но которой которой нет в другом.
Помогите Богдану посчитать количество маршрутов с каждой платформы. Так как количество маршрутов может быть очень большим, необходимо вывести остаток от деления количeства маршрутов на \(10^9 + 7\).
Первая строка содержит единственное целое число \(n\) (\(1 \le n \le 3 \cdot 10^5\)) — количество платформ.
Следующие \(n\) строк содержат описания платформ, \(i\)-я из них содержит два числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le 10^9\)) — концы отрезка \(i\)-й платформы.
Выведите \(n\) чисел, \(i\)-е число должно быть равно количеству различных маршрутов, начинающихся в платформе \(i\), взятое по модулю \(10^9 + 7\).
5 1 5 1 4 1 3 1 2 1 1
5 4 3 2 1
4 3 3 1 4 1 5 2 5
1 2 5 2