Help Yourself | Code Joint

Bessie has been given $N$ ( $1 \leq N \leq 1 0^{5}$ ) segments on a 1D number line. The $i$ th segment contains all reals $x$ such that $l_{i} \leq x \leq r_{i}$ .

Define the union of a set of segments to be the set of all $x$ that are contained within at least one segment. Define the complexity of a set of segments to be the number of connected regions represented in its union, raised to the power of $K$ ( $2 \leq K \leq 10$ ).

Bessie wants to compute the sum of the complexities over all $2^{N}$ subsets of the given set of $N$ segments, modulo $1 0^{9} + 7$ .

Normally, your job is to help Bessie. But this time, you are Bessie, and there is no one to help you. Help yourself!

SCORING

Test case 2 satisfies $N \leq 16$ .
Test cases 3-5 satisfy $N \leq 1000$ , $K = 2$ .
Test cases 6-8 satisfy $N \leq 1000$ .
For each $T \in [9, 16],$ test case $T$ satisfies $K = 3 + (T - 9)$ .

The complexity of each nonempty subset is written below.

{[1, 6]} ⟹ 1, {[2, 3]} ⟹ 1, {[4, 5]} ⟹ 1

{[1, 6], [2, 3]} ⟹ 1, {[1, 6], [4, 5]} ⟹ 1, {[2, 3], [4, 5]} ⟹ 4

{[1, 6], [2, 3], [4, 5]} ⟹ 1

The answer is $1 + 1 + 1 + 1 + 1 + 4 + 1 = 10$ .

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ and $K$ .

Each of the next $N$ lines contains two integers $l_{i}$ and $r_{i}$ . It is guaranteed that $l_{i} < r_{i}$ and all $l_{i}, r_{i}$ are distinct integers in the range $1 \dots 2 N .$

Output Format

Output the answer, modulo $1 0^{9} + 7$ .

Sample Input

3 2 1 6 2 3 4 5

Sample Output

10

Submit

Language