Cowmistry#10375
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 and can only be present in the same mixture if a \oplus b \leq k.
NOTE: Here, a \oplus b denotes the "bitwise exclusive or" of non-negative integers and . This operation is equivalent to adding each corresponding pair of bits in base and discarding the carry. For example,
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 has boxes of cow-michals and the -th box contains cow-michals labeled l_i through r_i inclusive. 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 (1 \leq n \leq 2 \cdot 10^4) and (1 \leq k \leq 10^9). Each of the next lines contains two space-separated integers l_i and r_i (0 \leq l_i \leq r_i \leq 10^9). It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, r_i < l_{i+1} for each 1 \leq i < n.
The number of mixtures of three different cow-michals Bessie can create, modulo 10^9 + 7.
Example 1
Example 2
We can split the chemicals into groups that cannot cross-mix: (), (), , (). Each of the first twelve groups contributes unique mixtures and the last contributes (since all C_8^3 combinations of three different cow-michals from () are okay), for a total of 352 \cdot 12 + 56 = 4280.