Булат отвечает за хранилище, которое образовано двумя бесконечными диагональными стенами, соединенными в одной точке внизу. В хранилище есть $$$n$$$ квадратных ящиков одинакового размера. Ящики естественно притягиваются силой тяжести. Например, расположение ящиков может быть следующим:
Затем нижний ящик убирается из хранилища. Другие ящики начинают падать в освободившееся пространство, пока снова не будет достигнуто стабильное расположение. Ящики могут падать по-разному, в зависимости от того, заполняет ли пустой слот левый или правый верхний ящик. Например, на предыдущем рисунке есть 3 разных варианта:
Помогите Булату найти общее количество различных возможных сценариев по модулю $$$10^9+7$$$.
Первая строка содержит единственное целое число, количество ящиков $$$n$$$ ($$$1 \leq n \leq 10^5$$$). Следующие $$$n$$$ строк описывают ящики, $$$i$$$-я из них содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$). Это координаты ящика в следующей системе координат: ряды ящиков, перпендикулярных левой стене хранилища, пронумерованы целыми числами, начиная с $$$1$$$, и мы обозначим эту ось через $$$x$$$; ряды ящиков, перпендикулярных правой стене хранилища, пронумерованы целыми числами, начиная с $$$1$$$, и обозначим эту ось через $$$y$$$. Ящик с координатами $$$(x_i,y_i)$$$ расположен на пересечении $$$x_i$$$-й и $$$y_i$$$-й таких строк соответственно.
Гарантируется, что данное расположение ящиков стабильно.
Выведите единственное целое число — количество возможных сценариев падения ящиков по модулю $$$10^9+7$$$.
51 11 22 23 12 1
3
