Problem Description

Bessie's chemistry homework has been overdue for a long time, and now she needs your help. She needs to make a mixture using three different chemicals. All smart cows know that some chemicals cannot be mixed together, or they will explode. Specifically, two chemicals labeled $a$ and $b$ can appear in the same mixture when $a⊕b≤K$ ($1≤K≤10^9$).

Note: Here, $a⊕b$ denotes the XOR of non-negative integers $a$ and $b$. This operation is equivalent to adding each corresponding bit in binary and discarding carries. For example,

,

,

.

Bessie has $N$ boxes of chemicals. The $i$-th box contains chemicals with labels from $l_i$ to $r_i$ ($0≤l_i≤r_i≤10^9$). No two boxes contain the same chemical. She wants to know how many different mixtures she can make that consist of three different chemicals. Two mixtures are considered different if there exists at least one chemical that appears in one mixture but not the other. Since the answer may be very large, output it modulo $10^9+7$.

Input Format

The first line contains two integers $N$ and $K$.

The next $N$ lines each contain two space-separated integers $l_i$ and $r_i$. It is guaranteed that the boxes are given in increasing order by their contents; that is, for all $1≤i<N$, we have $r_i<l_{i+1}$.

Output Format

Output the number of mixtures Bessie can make using three different chemicals, modulo $10^9+7$.

1 13
0 199

4280

6 147
1 35
48 103
125 127
154 190
195 235
240 250

267188

Hint

We can divide all chemicals into $13$ groups that cannot be mixed across groups: $(0 \ldots 15)$, $(16 \ldots 31)$, … $(192 \ldots 199)$. Each of the first $12$ groups contributes $352$ mixtures, and the last group contributes $56$ (because all $\binom{8}{3}$ combinations of three different chemicals in $(192 \ldots 199)$ are valid), for a total of $352 \cdot 12 + 56 = 4280$.

• Subtasks 3-4 satisfy $\max(K, r_N) \le {10}^4$.
• Subtasks 5-6 satisfy $K = 2^k - 1$ for some $k \ge 1$.
• Subtasks 7-11 satisfy $\max(K, r_N) \le {10}^6$.
• Subtasks 12-16 satisfy $N \le 20$.
• Subtasks 17-21 have no additional constraints.

For all subtasks, $1 \le N \le 2 \times {10}^4$.

Problem by: Benjamin Qi.

Translated by ChatGPT 5