# USACO 2020 December

# 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 ⊕ b** ≤ **k**.

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 = `101`

⊕ _{2}`111`

= _{2}`010`

= 2_{2}

Bessie has **n** boxes of cow-michals and the **i**-th box contains cow-michals labeled `l`

through _{i}`r`

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 _{i}`10`

+ ^{9}**7**.

#### Input

The first line contains two integers **n** (**1** ≤ **n** ≤ **2** * `10`

) and ^{4}**k** (**1** ≤ **k** ≤ `10`

). Each of the next ^{9}**n** lines contains two space-separated integers `l`

and _{i}`r`

(_{i}**0** ≤ `l`

≤ _{i}`r`

≤ _{i}`10`

). It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, ^{9}`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**.

#### 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**.

1 13 0 199

4280

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

267188