Bessie đã trì hoãn bài tập hóa học dành cho bò và giờ cần bạn giúp! Cô cần tạo một hỗn hợp gồm ba hóa chất bò khác nhau. Tuy nhiên, một số hóa chất không thể trộn với nhau vì sẽ gây nổ. Cụ thể, hai hóa chất mang nhãn \(a\) và \(b\) chỉ có thể cùng xuất hiện trong một hỗn hợp nếu \(a\oplus b\le K\) (\(1\le K\le 10^9\)).

Ở đây, \(a\oplus b\) là phép XOR theo bit của hai số nguyên không âm \(a\) và \(b\). Phép toán này tương đương với cộng từng cặp bit tương ứng trong hệ nhị phân rồi bỏ số nhớ. Ví dụ:

Bessie có \(N\) hộp hóa chất (\(1\le N\le 2\cdot10^4\)), và hộp thứ \(i\) chứa các hóa chất mang nhãn từ \(l_i\) đến \(r_i\), kể cả hai đầu (\(0\le l_i\le r_i\le 10^9\)). Không có hai hộp nào chứa chung hóa chất. Cô muốn biết có thể tạo bao nhiêu hỗn hợp khác nhau gồm ba hóa chất phân biệt. Hai hỗn hợp được coi là khác nhau nếu có ít nhất một hóa chất xuất hiện trong hỗn hợp này nhưng không xuất hiện trong hỗn hợp kia. Vì đáp án có thể rất lớn, hãy lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\), cách nhau bởi dấu cách. Các hộp được cho theo thứ tự tăng dần của nội dung; cụ thể, \(r_i<l_{i+1}\) với mọi \(1\le i<N\).

Dữ liệu ra

In số hỗn hợp gồm ba hóa chất phân biệt mà Bessie có thể tạo, lấy modulo \(10^9+7\).

Phân nhóm

• Các test 3-4 thỏa mãn \(\max(K,r_N)\le 10^4\).
• Các test 5-6 thỏa mãn \(K=2^k-1\) với một số nguyên \(k\ge 1\).
• Các test 7-11 thỏa mãn \(\max(K,r_N)\le 10^6\).
• Các test 12-16 thỏa mãn \(N\le 20\).
• Các test 17-21 không có ràng buộc bổ sung.

Ví dụ

1 13
0 199

4280

6 147
1 35
48 103
125 127
154 190
195 235
240 250

267188

Nguồn

USACO 2020 December Contest, Platinum - Cowmistry: https://usaco.org/index.php?page=viewproblem2&cpid=1070

Tác giả: Benjamin Qi.