Бесси получила отрезков на 1D числовой прямой. - ый отрезок содержит все вещественные числа такие, что . Определим объединение отрезков как набор всех , содержащихся хотя бы в одном из них. Определим сложность набора отрезков как количество связанных областей, представленных в его объединении.
Бесси хочет вычислить сумму сложностей по всем подмножествам данного набора из отрезков по модулю .
Обычно твоя работа — помогать Бесси. Но на этот раз ты Бесси, и помочь тебе некому. Помоги себе!
Первая строка содержит число . Каждая из следующих строк содержит два целых числа и . Гарантируется, что и все являются различными целыми числами в диапазоне .
Выведите ответ по модулю .
Сложность каждого непустого подмножества приведена ниже.
Ответ равен .