부분집합의 복잡도의 합

실행 시간 제한	메모리 제한
2 초	512 MB

한솔은 1차원 수직선에 위치한 $N$ ( $1 \le N \le 10^5$ )개의 선분을 가지고 있습니다. $i$ 번째 선분은 $l_i \le x \le r_i$ 인 모든 실수 $x$ 를 포함하고 있습니다.

한 세트의 선분들의 합집합을, 적어도 하나의 선분에 포함되는 모든 $x$ 들의 집합이라고 정의합시다.

그리고 세트의 복잡도를 그 합집합이 나타내는 연결된 영역의 개수를 $K$ ( $2 \le K \le 10$ ) 제곱한 값이라고 정의합시다.

한솔은 주어진 $N$ 개의 선분들의 모든 $2^N$ 개의 부분집합에 대한 복잡도의 합을 계산하고, 결과값을 $10^9+7$ 으로 나눈 나머지를 구하고 싶어합니다.

첫 번째 줄에는 $N$ 과 $K$ 가 주어집니다.

다음 $N$ 줄 각각에는 두 정수 $l_i$ 와 $r_i$ 이 주어집니다.

$l_i \lt r_i$ 이며, 모든 $l_i, r_i$ 는 $1 \ldots 2N.$ 범위 내의 서로 다른 정수입니다.

답을 출력하세요. 결과값은 $10^9+7$ 로 나눈 나머지입니다.

각 비어있지 않은 부분집합의 복잡도는 아래와 같습니다.

$\{[1,6] \} \implies 1, \{[2,3] \} \implies 1, \{[4,5] \} \implies 1$

$\{[1,6],[2,3] \} \implies 1, \{[1,6],[4,5] \} \implies 1, \{[2,3],[4,5] \} \implies 4$

$\{[1,6],[2,3],[4,5] \} \implies 1$

답은 $1+1+1+1+1+4+1=10$ 입니다.