Cowmistry--Plat 翻译

题目翻译
Bessie 的化学混合物
Bessie 一直在拖延她的化学作业，现在需要你的帮助！她需要配制一种由三种不同化学物质混合而成的混合物。众所周知，有些化学物质不能混合在一起，否则会发生爆炸。具体来说，标签为 a 和 b 的两种化学物质只有在满足 a⊕b≤K （1≤K≤10
9
）时才能共存于同一混合物中。
注意： 这里 a⊕b 表示非负整数 a 和 b 的按位异或。这个操作等价于将两个数在二进制下逐位相加并忽略进位。例如：
0⊕0=1⊕1=0
1⊕0=0⊕1=1
5⊕7=101
2
​
⊕111
2
​
=010
2
​
=2
Bessie 有 N （1≤N≤2⋅10
4
）盒化学物质，第 i 盒中含有标签从 l
i
​
到 r
i
​
（包含端点，0≤l
i
​
≤r
i
​
≤10
9
）的化学物质。任意两盒之间没有共同的化学物质。她想知道可以配制出多少种不同的由三种不同化学物质组成的混合物。如果两种混合物中至少有一种化学物质只出现在其中一种混合物中，则认为这两种混合物是不同的。由于答案可能非常大，请输出答案对 10
9
+7 取模的结果。
输入格式
第一行包含两个整数 N 和 K 。
接下来的 N 行，每行包含两个用空格隔开的整数 l
i
​
和 r
i
​
。保证盒子按内容递增顺序给出，即对于每个 1≤i<N ，都有 r
i
​
<l
i+1
​
。
输出格式
输出 Bessie 可以配制的由三种不同化学物质组成的混合物的数量，对 10
9
+7 取模。
输入输出样例
输入 #1
plain
1 13
0 199
输出 #1
plain
4280
说明/提示
我们可以将这些化学物质分成 13 个不能交叉混合的组：(0…15) 、(16…31) 、……、(192…199) 。前 12 个组每组贡献 352 种不同的混合物，最后一组贡献 56 种（因为从 (192…199) 中任选 3 种不同的化学物质都是可以的），总共 352×12+56=4280 。