Cowmistry

Time limit1sMemory limit512 MB

Summary

Count the sets of three distinct labels, taken from N disjoint integer intervals, where every pair has XOR at most K, modulo 1e9+7.

Level: Hard8 of 10
Topics: Bit manipulation, Divide and conquer, Combinatorics
Solved: No attempts yet

Problem

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. Two cow-michals with labels $a$ and $b$ can only be present in the same mixture if $a \oplus b \le K$ ( $1 \le K \le 10^9$ ).

NOTE: Here, $a\oplus b$ denotes the bitwise exclusive or of non-negative integers $a$ and $b$ . This operation adds each corresponding pair of bits in base 2 and discards the carry. For example,

$0\oplus 0=1\oplus 1=0,$ $1\oplus 0=0\oplus 1=1,$ $5\oplus 7=101_2\oplus 111_2=010_2=2.$

Bessie has $N$ ( $1\le N\le 2\cdot 10^4$ ) boxes of cow-michals. The $i$ -th box contains cow-michals labeled $l_i$ through $r_i$ inclusive ( $0\le l_i \le r_i \le 10^9$ ). No two boxes share a cow-michal. She wants to know how many unique mixtures of three different cow-michals she can create. Two mixtures are different if at least one cow-michal is present in one but not the other. Since the answer may be very large, report it modulo $10^9 + 7$ .

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$ . The boxes are given in increasing order of their contents, so $r_i < l_{i+1}$ for each $1 \le i < N$ .

Output

Print the number of mixtures of three different cow-michals Bessie can create, modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
1 13
0 199
```
Expected output
```
4280
```

Example 2

Input

Expected output