Help Yourself (Platinum)#10607

Help Yourself (Platinum)

1 second

128 megabytes

Very hard

Bessie has been given $n$ segments on a 1D number line. The $i$ -th segment contains all reals $x$ such that $l_{i} \leq x \leq r_{i}$ 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$ .

Bessie wants to compute the sum of the complexities over all $2^{n}$ 2^n subsets of the given set of $n$ segments, modulo $1 0^{9} + 7$ 10^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!

Input

The first line contains $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) and $k$ ( $2 \leq k \leq 10$ 2 \leq k \leq 10). Each of the next $n$ lines contains two integers $l_{i}$ l_i and $r_{i}$ r_i. It is guaranteed that $l_{i} < r_{i}$ l_i < r_i and all $l_{i}$ l_i, $r_{i}$ r_i are distinct integers in the range $1..2 n$ .

Output

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

Examples

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$ 1 + 1 + 1 + 1 + 1 + 4 + 1 = 10.

Example 1