카우미스트리

Bessie는 화학 숙제를 계속 미뤄 두었고 이제 당신의 도움이 필요하다. 그녀는 서로 다른 세 종류의 cow-michal을 섞어 혼합물을 만들어야 한다. 그런데 현명한 소들이 아는 것처럼, 일부 cow-michal은 서로 섞으면 폭발하므로 같은 혼합물에 넣을 수 없다. 라벨이 $a$와 $b$인 두 cow-michal은 $a \oplus b \le K$일 때에만 같은 혼합물에 들어갈 수 있다 ($1 \le K \le 10^9$).

NOTE: 여기서 $a\oplus b$는 음이 아닌 정수 $a$와 $b$의 비트 단위 배타적 논리합(XOR)을 뜻한다. 이 연산은 2진수에서 같은 자리의 비트끼리 더하되 올림은 버린다. 예를 들어,

$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는 cow-michal이 담긴 상자를 $N$개($1\le N\le 2\cdot 10^4$) 가지고 있다. $i$번째 상자에는 라벨이 $l_i$부터 $r_i$까지(양 끝 포함) 붙은 cow-michal이 들어 있다($0\le l_i \le r_i \le 10^9$). 두 상자에 같은 cow-michal은 없다. 그녀가 만들 수 있는 서로 다른 세 cow-michal의 혼합물이 모두 몇 가지인지 구하라. 두 혼합물은 한쪽에만 들어 있는 cow-michal이 하나라도 있으면 서로 다른 것으로 본다. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 두 정수 $N$과 $K$가 주어진다.

이어지는 $N$개의 줄에는 각각 공백으로 구분된 두 정수 $l_i$와 $r_i$가 주어진다. 상자는 내용물의 순서대로 주어지며, 각 $1 \le i < N$에 대해 $r_i < l_{i+1}$이다.

Bessie가 만들 수 있는 서로 다른 세 cow-michal 혼합물의 개수를 $10^9 + 7$로 나눈 나머지로 출력한다.