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 $aa$ and $bb$ can only be present in the same mixture if $a\oplus b\le Ka\; \backslash oplus\; b\; \backslash le\; K$ ($1\le K\le {10}^{9}1\; \backslash le\; K\; \backslash le\; 10^9$).

NOTE: Here, $a\oplus ba\backslash oplus\; b$ denotes the "bitwise exclusive or" of non-negative integers $aa$ and $bb$. This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,

Bessie has $NN$ ($1\le N\le 2\cdot {10}^{4}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^4$) boxes of cow-michals and the $ii$-th box contains cow-michals labeled $l_{i}l\_i$ through $r_{i}r\_i$ inclusive $(0\le l_i\le r_i\le {10}^9)(0\backslash le\; l\_i\; \backslash le\; r\_i\; \backslash le\; 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+710^9\; +\; 7$.

입력

The first line contains two integers $NN$ and $KK$.

Each of the next $NN$ lines contains two space-separated integers $l_{i}l\_i$ and $r_{i}r\_i$. It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, for each .

출력

The number of mixtures of three different cow-michals Bessie can create, modulo ${10}^9+710^9\; +\; 7$.

1 13
0 199

4280

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

267188