8102: USACO 2020 December Contest, Platinum Problem 3. Cowmistry
[Creator : ]
Description
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,
Bessie has $N\ (1≤N≤2⋅10^4)$ boxes of cow-michals and the i-th box contains cow-michals labeled $l_i$ through $r_i$ 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$.
$$0⊕0=1⊕1=0,$$
$$1⊕0=0⊕1=1,$$
$$5⊕7=101_2⊕111_2=010_2=2.$$
Input
The first line contains two integers N and K. Each of the next N lines contains two space-separated integers $l_i$ and $r_i$.
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≤i<N$.
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≤i<N$.
Output
The number of mixtures of three different cow-michals Bessie can create, modulo $10^9+7$.
Sample 1 Input
1 13
0 199
Sample 1 Output
4280
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 $(^8_3)$ combinations of three different cow-michals from (192…199) are okay), for a total of 352⋅12+56=4280.
Sample 2 Input
6 147
1 35
48 103
125 127
154 190
195 235
240 250
Sample 2 Output
267188