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