Бесі потребує Вашої допомоги. Вона має створити мікстуру із трьох різних компонентів. Деякі компоненти не можна змішувати один з одним. Зокрема, дві компоненти з мітками \(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\)) ящиків з компонентами. ящик містить компоненти з номерами від \(l_i\) до \(r_i\) включно \((0\le l_i \le r_i \le 10^9)\). Жодні два ящики не містять однакових компонентів. Бесі хоче дізнатися, скільки унікальних мікстур із трьох різних компонентів вона може створити. Дві мікстури розглядаються як різні, якщо хоча б одна компонента є в одній мікстурі та відсутня в іншій. Відповідь виводьте за модулем \(10^9 + 7\).

Формат вхідних даних

Перший рядок містить два цілих числа \(N\) і \(K\).

Кожен з наступних \(N\) рядків містить два розділені пробілом цілих числа \(l_i\) і \(r_i\). Гарантується, що ящики даються в порядку зростання вмісту. а саме , \(r_i<l_{i+1}\) для кожного \(1\le i<N\).

Формат вихідних даних

Кількість мікстур із трьох різних компонентів, які Бесі може створити за модулем \(10^9 + 7\).

Приклад вхідних даних

 1 13
 0 199

Приклад вихідних даних

 4280

Ми можемо розділити компоненти на 13 груп, які не можуть перетинатися: \((0 \ldots 15)\), \((16 \ldots 31)\), ... \((192 \ldots 199)\). Кожна з перших 12 груп дає \(352\) унікальні мікстури, а остання - 56 оскільки \(\binom{8}{3}\) з трьох різних компонент \( (192 \ldots 199) \) всього \( 352 \cdot 12 +56 = 4280 \).

Приклад вхідних даних

6 147
1 35
48 103
125 127
154 190
195 235
240 250

Приклад вихідних даних

267188

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 немає додаткових обмежень.