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

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

0 ⊕ 0 = 1 ⊕ 1 = 0,

1 ⊕ 0 = 0 ⊕ 1 = 1,

5 ⊕ 7 = 1012 ⊕ 1112 = 0102 = 2

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

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 2 * 104) и k (1 ≤ k ≤ 109). Каждая из следующих n строк содержит два целых числа li и ri (0 ≤ li ≤ ri ≤ 109). Гарантируется, что ящики с коровьим кормом предоставляются в порядке возрастания их содержимого; а именно, ri < li + 1 для каждого 1 ≤ i < n.

Выходные данные

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

Пример

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