Problem Description

There are $N$ line segments on a number line. The $i$-th segment covers all real numbers from $l_i$ to $r_i$ (including $l_i$ and $r_i$).

Define the union of several segments as the set containing all points that are covered by at least one segment.

Define the complexity of several segments as the $K$-th power of the number of connected components in the union of these segments.

Now Bessie wants to compute, among all subsets of the given $N$ segments (there are $2^N$ subsets in total), the sum of their complexities modulo $10^9+7$.

You might think you need to help Bessie solve this problem. Unfortunately, you guessed wrong! In this problem, you are Bessie, and no one will help you. You are on your own.

Input Format

The first line contains two integers $N$ and $K$ ($1 \leq N \leq 10^5$; $2 \leq K \leq 10$).

The next $N$ lines each contain two integers $l_i, r_i$, describing a segment. It is guaranteed that $1 \leq l_i \lt r_i \leq 2N$, and no two endpoints are at the same position.

Output Format

Output the required answer modulo $10^9+7$.

3 2
1 6
2 3
4 5

10

Hint

Sample Explanation

The complexities of all non-empty subsets are as follows (clearly, the complexity of the empty set is zero):

$$\{[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$$

Therefore, the answer is $1+1+1+1+1+4+1=10$.

Subtasks

• Test point $2$ satisfies $N \leq 16$.
• Test points $3 \sim 5$ satisfy $N \leq 10^3$ and $K=2$.
• Test points $6 \sim 8$ satisfy $N \leq 10^3$.
• For test point $T$ ($T \in [9,16]$), $K=3+(T-9)$.

Translated by ChatGPT 5