题目描述

Bessie 的化学作业已经拖了很久，现在需要你的帮助！她需要用三种不同的化学品制造一种混合物。所有聪明的奶牛都知道，某些化学品之间不能进行混合，否则会产生爆炸。具体地说，两种标号为 $a$ 和 $b$ 的化学品当 $a \oplus b \leq K$（$1 \leq K \leq 10^9$）时可以出现在同一种混合物中。

注：这里，$a \oplus b$ 表示非负整数 $a$ 与 $b$ 的「异或」。这一运算等价于在二进制下将每一对应位相加并且舍弃进位。例如：

• $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 有 $N$ ($1 \leq N \leq 2 \times 10^4$) 盒化学品，第 $i$ 个盒子内有标号从 $l_i$ 到 $r_i$ 的化学品（$0 \leq l_i \leq r_i \leq 10^9$）。没有两个盒子中含有同一种化学品。她想要知道她可以得到多少种由三种不同的化学品混合而成的混合物。如果至少一种化学品出现在一种混合物中而没有出现在另一种中，则认为这两种混合物是不同的。由于答案可能非常大，输出对 $10^9+7$ 取模的结果。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$。

以下 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证所有化学品盒子按其中内容的升序给出；也就是说，对所有 $1 \leq i < N$ 有 $r_i < l_{i+1}$。

输出格式

输出 Bessie 可以由三种不同化学品制造的混合物的数量，对 $10^9+7$ 取模。

样例 1

输入 1 13 0 199

text

输出 4280

text

我们可以将所有化学品分为不能交叉混合的 $13$ 组：$(0 \dots 15)$，$(16 \dots 31)$，$\dots$ $(192 \dots 199)$。前 $12$ 组每组贡献了 $352$ 种混合物，最后一组贡献了 $56$ 种（因为所有 $\binom{8}{3}$ 种 $(192 \dots 199)$ 中三种不同化学品的组合均可行），总共为 $352 \cdot 12 + 56 = 4280$。

样例 2

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

text

输出 267188

text

数据范围与提示

• 测试点 $3 \sim 4$ 满足 $\max(K, r_N) \leq 10^4$。
• 测试点 $5 \sim 6$ 对某个 $k \geq 1$ 满足 $K = 2^k - 1$。
• 测试点 $7 \sim 11$ 满足 $\max(K, r_N) \leq 10^6$。
• 测试点 $12 \sim 16$ 满足 $N \leq 20$。
• 测试点 $17 \sim 21$ 没有额外限制。