Bessie 一直在拖延她的“牛学”作业，现在需要你的帮助！她需要混合三种不同的“牛学”化学物质。众所周知，有些化学物质不能混合在一起，否则会引起爆炸。具体来说，两个标签分别为 $a$ 和 $b$ 的化学物质，仅当 $a \oplus b \le K$ ($1 \le K \le 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\le N\le 2\cdot 10^4$) 个装有化学物质的盒子，第 $i$ 个盒子包含标签从 $l_i$ 到 $r_i$（包含边界）的化学物质 $(0\le l_i \le r_i \le 10^9)$。任意两个盒子之间没有共同的化学物质。她想知道她可以创造出多少种三种不同化学物质的独特混合物。如果两种混合物中至少有一种化学物质不同，则认为它们是不同的。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

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

接下来的 $N$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$。保证盒子按其内容物的递增顺序给出，即对于每个 $1\le i

输出格式

Bessie 可以创造的三种不同化学物质的混合物数量，对 $10^9 + 7$ 取模。

样例

样例输入 1

1 13
0 199

样例输出 1

4280

说明 1

我们可以将化学物质分为 13 组，组间不能混合：$(0\ldots 15)$, $(16\ldots 31)$, $\ldots$ $(192\ldots 199)$。前十二组每组贡献 $352$ 种独特的混合物，最后一组贡献 $56$ 种（因为从 $(192\ldots 199)$ 中选出三种不同化学物质的所有 $\binom{8}{3}$ 种组合都是合法的），总计 $352\cdot 12+56=4280$。

样例输入 2

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

样例输出 2

267188

子任务

• 测试点 3-4 满足 $\max(K,r_N)\le 10^4$。
• 测试点 5-6 满足 $K=2^k-1$，其中 $k\ge 1$ 为整数。
• 测试点 7-11 满足 $\max(K,r_N)\le 10^6$。
• 测试点 12-16 满足 $N\le 20$。
• 测试点 17-21 满足无额外限制。

题目来源：Benjamin Qi