Help Yourself (Platinum)

Bessie에게 1차원 수직선 위의 $N$개 ($1\le N\le 10^5$) 선분이 주어진다. $i$번째 선분은 $l_i\le x\le r_i$인 모든 실수 $x$를 포함한다.

선분 집합의 합집합은 그중 적어도 하나의 선분에 포함되는 모든 $x$의 집합이다. 선분 집합의 복잡도는 합집합에 나타나는 연결된 영역의 개수를 $K$제곱한 값이다 ($2\le K\le 10$).

Bessie는 주어진 $N$개 선분의 모든 $2^N$개 부분집합에 대한 복잡도의 합을 $10^9+7$로 나눈 나머지를 구하려고 한다.

평소라면 여러분이 Bessie를 돕는 입장이다. 하지만 이번에는 여러분이 Bessie이고, 도와줄 사람이 없다. 스스로 해결하자!

첫째 줄에 $N$과 $K$가 주어진다.

다음 $N$개 줄에 각각 두 정수 $l_i$와 $r_i$가 주어진다. $l_i< 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$이다.