Крадіжка
Бессі відкладала виконання домашнього завдання з коров'ячого господарства, і тепер їй потрібна твоя допомога! Їй потрібно створити суміш з трьох різних коров'ячих кормів. Однак, як відомо всім хорошим коровам, деякі коров'ячі корми не можна змішувати один з одним, інакше вони викличуть вибух. Зокрема, два коров'ячі корми з мітками 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 сумішей.