Nhân Bản Hóa Học

Bác sĩ hóa học Bessie đang nghiên cứu $N$ hộp hóa chất. Hộp thứ $i$ chứa các hóa chất được đánh nhãn từ $l_i$ đến $r_i$ (mỗi nhãn là một số nguyên). Các hộp không giao nhau và được sắp xếp theo thứ tự tăng dần (tức là $r_i<l_{i+1}$ với mọi $i$).

Một hỗn hợp gồm 3 hóa chất khác nhau $\{x,y,z\}$ được gọi là hợp lệ nếu tất cả các XOR từng cặp đều không vượt quá $K$, tức là:

• $$x\oplus y\le K,x\oplus z\le K,y\oplus z\le K$$

Đếm số lượng bộ ba hóa chất hợp lệ (không phân biệt thứ tự), lấy phần dư cho ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $K$.
• $N$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $l_i$ và $r_i$.

Dữ liệu ra

Một số nguyên duy nhất là số lượng bộ ba hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 2\times {10}^4$
• $0\le K\le {10}^9$
• $0\le l_i\le r_i\le {10}^9$
• Các hộp không giao nhau và được sắp theo thứ tự: $r_i<l_{i+1}$

Ví dụ

Ghi chú

• Ba hóa chất $x,y,z$ phải khác nhau (khác nhãn).
• Hóa chất trong các hộp khác nhau có nhãn khác nhau (do hộp không giao nhau).
• Bộ ba $\{x,y,z\}$ không phân biệt thứ tự, tức là $\{1,2,3\}$ và $\{3,1,2\}$ được coi là một.