Competitions

# Cowmistry

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 ⊕ bk.

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 = 10121112 = 0102 = 2

Bessie has n boxes of cow-michals and the i-th box contains cow-michals labeled li through ri 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 109 + 7.

#### Input

The first line contains two integers n (1n2 * 104) and k (1k109). Each of the next n lines contains two space-separated integers li and ri (0liri109). It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, ri < li + 1 for each 1i < n.

#### Output

The number of mixtures of three different cow-michals Bessie can create, modulo 109 + 7.

#### Example

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 C3_8 combinations of three different cow-michals from (192...199) are okay), for a total of 352 * 12 + 56 = 4280.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 13
0 199

Output example #1
4280

Input example #2
6 147
1 35
48 103
125 127
154 190
195 235
240 250

Output example #2
267188

Source 2020 USACO December, Platinum