Бесси получила n отрезков на 1D числовой прямой. i - ый отрезок содержит все вещественные числа x такие, что li≤x≤ri. Определим объединение отрезков как набор всех x, содержащихся хотя бы в одном из них. Определим сложность набора отрезков как количество связанных областей, представленных в его объединении.
Бесси хочет вычислить сумму сложностей по всем 2n подмножествам данного набора из n отрезков по модулю 109+7.
Обычно твоя работа — помогать Бесси. Но на этот раз ты Бесси, и помочь тебе некому. Помоги себе!
Первая строка содержит число n (1≤n≤105). Каждая из следующих n строк содержит два целых числа li и ri. Гарантируется, что li<ri и все li,ri являются различными целыми числами в диапазоне 1...2n.
Выведите ответ по модулю 109+7.
Сложность каждого непустого подмножества приведена ниже.
Ответ равен 1+1+1+1+1+2+1=8.