eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Коровство

Коровство

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Бесси откладывала домашнее задание по коровьему хозяйству, и теперь ей нужна твоя помощь! Ей нужно создать смесь из трех разных коровьих кормов. Однако, как известно всем хорошим коровам, некоторые коровьи корма нельзя смешивать друг с другом, иначе они вызовут взрыв. В частности, два коровьих корма с метками a и b могут присутствовать в одной и той же смеси, только если a ⊕ bk.

ПРИМЕЧАНИЕ. Здесь a ⊕ b обозначает "побитовое исключающее or" неотрицательных целых чисел a и b. Эта операция эквивалентна сложению каждой соответствующей пары битов по основанию 2 без учета переноса. Например,

0 ⊕ 0 = 1 ⊕ 1 = 0,

1 ⊕ 0 = 0 ⊕ 1 = 1,

5 ⊕ 7 = 101[2]111[2] = 010[2] = 2

У Бесси есть n ящиков с коровьими кормами, i -ая коробка содержит корма, помеченные от l[i] до r[i] включительно. Никакие две коробки не имеют общих коровьих кормов. Она хочет знать, сколько уникальных смесей из трех разных коровьих кормов она может создать. Две смеси считаются разными, если в одной присутствует хотя бы один коровий корм, а в другой нет. Поскольку ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Вхідні дані

Первая строка содержит два целых числа n (1n2 * 10^4) и k (1k10^9). Каждая из следующих n строк содержит два целых числа l[i] и r[i] (0l[i]r[i]10^9). Гарантируется, что ящики с коровьим кормом предоставляются в порядке возрастания их содержимого; а именно, r[i] < l[i] + 1 для каждого 1i < n.

Вихідні дані

Выведите количество смесей трех разных кормов, которые Бесси может создать, по модулю 10^9 + 7.

Пример

Мы можем разделить химические вещества на 13 групп, которые не могут быть смешаны: (0...15), (16...31), ... (192...199). Каждая из первых двенадцати групп даст 352 уникальные смеси, а последняя даст 56 (поскольку все C3_8 комбинаций трех разных смесей из (192 ... 199) возможны), всего получим 352 * 12 + 56 = 4280 смесей.

Приклад

Вхідні дані #1
1 13
0 199
Вихідні дані #1
4280
Вхідні дані #2
6 147
1 35
48 103
125 127
154 190
195 235
240 250
Вихідні дані #2
267188
Джерело 2020 USACO Декабрь, Платина