时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Bessie has been procrastinating on her cow-mistry homework and now needs your help! She needs to create a mixture of three different cow-michals. As all good cows know though, some cow-michals cannot be mixed with each other or else they will cause an explosion. In particular, two cow-michals with labels a and b can only be present in the same mixture if a⊕b≤K (1≤K≤10
9).
NOTE: Here, a⊕b denotes the "bitwise exclusive or'' of non-negative integers a and b. This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,
0⊕0=1⊕1=0,
1⊕0=0⊕1=1,
5⊕7=1012⊕1112=0102=2.
Bessie has N (1≤N≤2⋅10
4) boxes of cow-michals and the i-th box contains cow-michals labeled li through ri inclusive (0≤l
i≤r
i≤10
9). No two boxes have any cow-michals in common. She wants to know how many unique mixtures of three different cow-michals she can create. Two mixtures are considered different if there is at least one cow-michal present in one but not the other. Since the answer may be very large, report it modulo 10
9+7.
输入描述:
The first line contains two integers N and K.
Each of the next N lines contains two space-separated integers li and ri. It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, ri<li+1 for each 1≤i<N.
输出描述:
The number of mixtures of three different cow-michals Bessie can create, modulo 109+7.
示例1
说明
We can split the chemicals into 13 groups that cannot cross-mix: (0…15), (16…31), … (192…199). Each of the first twelve groups contributes 352 unique mixtures and the last contributes 56 (since all (83) combinations of three different cow-michals from (192…199) are okay), for a total of 352⋅12+56=4280.
示例2
输入
复制
6 147
1 35
48 103
125 127
154 190
195 235
240 250
说明
Test cases 3-4 satisfy max(K,rN)≤104.
Test cases 5-6 satisfy K=2k−1 for some integer k≥1.
Test cases 7-11 satisfy max(K,rN)≤106.
Test cases 12-16 satisfy N≤20.
Test cases 17-21 satisfy no additional constraints.
Problem credits: Benjamin Qi