Бесси откладывала домашнее задание по коровьему хозяйству, и теперь ей нужна твоя помощь! Ей нужно создать смесь из трех разных коровьих кормов. Однако, как известно всем хорошим коровам, некоторые коровьи корма нельзя смешивать друг с другом, иначе они вызовут взрыв. В частности, два коровьих корма с метками a и b могут присутствовать в одной и той же смеси, только если a ⊕ b ≤ k.
ПРИМЕЧАНИЕ. Здесь 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 (1 ≤ n ≤ 2 * 10^4
) и k (1 ≤ k ≤ 10^9
). Каждая из следующих n строк содержит два целых числа l[i]
и r[i]
(0 ≤ l[i]
≤ r[i]
≤ 10^9
). Гарантируется, что ящики с коровьим кормом предоставляются в порядке возрастания их содержимого; а именно, r[i]
< l[i]
+ 1 для каждого 1 ≤ i < n.
Выведите количество смесей трех разных кормов, которые Бесси может создать, по модулю 10^9
+ 7.
Мы можем разделить химические вещества на 13 групп, которые не могут быть смешаны: (0...15), (16...31), ... (192...199). Каждая из первых двенадцати групп даст 352 уникальные смеси, а последняя даст 56 (поскольку все C3_8 комбинаций трех разных смесей из (192 ... 199) возможны), всего получим 352 * 12 + 56 = 4280 смесей.