Коров'яча хімія#10375

Коров'яча хімія

1 секунда

128 мегабайтів

Легка

Бессі відкладала виконання домашнього завдання з коров'ячої хімії, і тепер їй потрібна твоя допомога! Їй потрібно створити суміш із трьох різних коров'ячих хімікатів. Однак, як відомо всім хорошим коровам, деякі коров'ячі хімікати не можна змішувати один з одним, інакше вони викличуть вибух. Зокрема, два коров'ячі хімікати з мітками $a$ і $b$ можуть бути присутні в одній і тій же суміші, тільки якщо $a \oplus b \leq k$ a \oplus b \leq k.

ПРИМІТКА. Тут $a \oplus b$ a \oplus b позначає "побітове виключне or" невід'ємних цілих чисел $a$ і $b$ . Ця операція еквівалентна додаванню кожної відповідної пари бітів за основою $2$ без урахування переносу. Наприклад,

$0 \oplus 0 = 1 \oplus 1 = 0$ 0 \oplus 0 = 1 \oplus 1 = 0,

$1 \oplus 0 = 0 \oplus 1 = 1$ 1 \oplus 0 = 0 \oplus 1 = 1,

$5 \oplus 7 = 10 1_{2} \oplus 11 1_{2} = 01 0_{2} = 2$ 5 \oplus 7 = 101_{2} \oplus 111_{2} = 010_{2} = 2

У Бессі є $n$ ящиків з коров'ячими хімікатами, $i$ -та коробка містить хімікати, позначені від $l_{i}$ l_i до $r_{i}$ r_i включно. Жодні дві коробки не мають спільних коров'ячих хімікатів. Вона хоче знати, скільки унікальних сумішей з трьох різних коров'ячих хімікатів вона може створити. Дві суміші вважаються різними, якщо в одній присутній хоча б один коров'ячий хімікат, а в іншій — ні. Оскільки відповідь може бути дуже великою, виведіть її за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить два цілі числа $n$ ( $1 \leq n \leq 2 \cdot 1 0^{4}$ 1 \leq n \leq 2 \cdot 10^4) і $k$ ( $1 \leq k \leq 1 0^{9}$ 1 \leq k \leq 10^9). Кожен із наступних $n$ рядків містить два цілі числа $l_{i}$ l_i і $r_{i}$ r_i ( $0 \leq l_{i} \leq r_{i} \leq 1 0^{9}$ 0 \leq l_i \leq r_i \leq 10^9). Гарантується, що ящики з коров'ячими хімікатами подаються у порядку зростання їх вмісту; а саме, $r_{i} < l_{i + 1}$ r_i < l_{i+1} для кожного $1 \leq i < n$ 1 \leq i < n.

Вихідні дані

Виведіть кількість сумішей трьох різних хімікатів, які Бессі може створити, за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Приклад 2

Примітка

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