Problem 3. Cowmistry

USACO 2020 December Contest, Platinum

Bessie 的化学作业已经拖了很久，现在需要你的帮助！她需要用三种不同的化学品制造一种混合物。所有聪明的奶牛都知道，某些化学品之间不能进行混合，否则会产生爆炸。具体地说，两种标号为 $a$ 和 $b$ 的化学品当 $a \oplus b \le K$ （$1 \le K \le 10^9$） 时可以出现在同一种混合物中。

注：这里，$a\oplus b$ 表示非负整数 $a$ 与 $b$ 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如，

$$0\oplus 0=1\oplus 1=0$$， $$1\oplus 0=0\oplus 1=1$$， $$5\oplus 7=101_2\oplus 111_2=010_2=2$$。 Bessie 有 $N$ 盒化学品，第 $i$ 个盒子内有标号从 $l_i$ 到 $r_i$ 的化学品（$0\le l_i \le r_i \le 10^9$）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对 $10^9 + 7$ 取模的结果。 ### 输入格式（从终端/标准输入读入）： 输入的第一行包含两个整数 $N$ 和 $K$。 以下 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 $1\le i<N$ 有 $r_i<l_{i+1}$。 ### 输出格式（输出至终端/标准输出）： 输出 Bessie 可以由三种不同化学品制造的混合物的数量，对 $10^9 + 7$ 取模。 <h4>输入样例：</h4> <pre class='in'> 1 13 0 199 </pre> <h4>输出样例：</h4> <pre class='out'> 4280 </pre> 我们可以将所有化学品分为不能交叉混合的 13 组：$(0\ldots 15)$， $(16\ldots 31)$，$\ldots$ $(192\ldots 199)$。前 12 组每组贡献了 $352$ 种混合物，最后一组贡献了 $56$ 种（因为所有 $\binom{8}{3}$ 种 $(192\ldots 199)$ 中三种不同化学品的组合均可行），总共为 $352\cdot 12+56=4280$。 <h4>输入样例：</h4> <pre class='in'> 6 147 1 35 48 103 125 127 154 190 195 235 240 250 </pre> <h4>输出样例：</h4> <pre class='out'> 267188 </pre> 测试点性质： 测试点 3-4 满足 $\max(K,r_N)\le 10^4$。测试点 5-6 对某个 $k\ge 1$ 满足 $K=2^k-1$。测试点 7-11 满足 $\max(K,r_N)\le 10^6$。测试点 12-16 满足 $N\le 20$。测试点 17-21 没有额外限制。 供题：Benjamin Qi$$