Беси дали \(N\) отрезков (\(1\le N\le 10^5\))и одну прямую. \(i\)-ый отрезок
содержит все вещественные числа \(x\) такие, что \(l_i\le x\le r_i\).
Определите объединение отрезов, которое будет множеством всех
\(x\) которые содержатся внутри хотя бы одного отрезка.
также определите сложность множества отрезков
как количество связанных отрезков, представленных в этом объединении.
Беси хочет вычислить сумму сложностей во всем \(2^N\) подмножествам заданного
множества из \(N\) отрезков по модулю \(10^9+7\).
Помогите Беси!
ОЦЕНИВАНИЕ:
- В тестах 2-3 \(N\le 16\).
- В тестах 4-7 \(N\le 1000\).
- В тестах 8-12 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл help.in):
Первая строка содержит
\(N\).
Каждая из следующих \(N\) строк содержит по два целых числа \(l_i\) и \(r_i\).
Гарантируется, что \(l_i< r_i\) и все \(l_i,r_i\) различные целые числа в интервале
\(1 \ldots 2N.\)
ФОРМАТ ВЫВОДА (файл help.out):
Выведите ответ по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 6
2 3
4 5
|
8
|