Беси нуждается в Вашей помощи.
Она должна создать микстуру из трёх различных компонент.
Некоторые из компонент нельзя смешивать друг с другом.
В частности, две компоненты с метками \(a\) и \(b\) могут присутствовать
в одной микстуре, только если \(a \oplus b \le K\) (\(1 \le K \le 10^9\)).
Замечание: Здесь, \(a\oplus b\) обозначает побитовое исключающее ИЛИ неотрицательных
целых чисел \(a\) и \(b\). Эта операция эквивалентна сложению соответствующих пар битов
по модулю 2 и игнорированию переноса. Например
\[0\oplus 0=1\oplus 1=0,\]
\[1\oplus 0=0\oplus 1=1,\]
\[5\oplus 7=101_2\oplus 111_2=010_2=2.\]
У Беси есть \(N\) (\(1\le N\le 2\cdot 10^4\)) ящиков с компонентами.
\(i\)-ый ящик содержит компоненты с номерами от \(l_i\) до \(r_i\) включительно
\((0\le l_i \le r_i \le 10^9)\). Никакие два ящика не содержат одинаковые компоненты.
Беси хочет узнать, сколько уникальных микстур из трёх различных компонент она может создать.
Две микстуры рассматриваются как различные, если хотя бы одна компонента есть в одной микстуре и
отсутствует в другой. Ответ выводите по модулю \(10^9 + 7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два целых числа
\(N\) и
\(K\).
Каждая из последующих \(N\) строк содержит два разделённых пробелом целых числа
\(l_i\) и \(r_i\). Гарантируется, что ящики даются в порядке возрастания содержимого.
а именно , \(r_i<l_{i+1}\) для каждого \(1\le i<N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество микстур из трёх различных компонент, которые Беси может создать по модулю
\(10^9 + 7\).
SCORING
- В тестах 3-4 \(\max(K,r_N)\le 10^4\).
- В тестах 5-6 \(K=2^k-1\) для некоторого целого \(k\ge 1\).
- В тестах 7-11 \(\max(K,r_N)\le 10^6\).
- В тестах 12-16 \(N\le 20\).
- В тестах 17-21 нет дополнительных ограничений.