eolymp
bolt
Try our new interface for solving problems
Problems

Help Yourself (Platinum)

Help Yourself (Platinum)

Time limit 1 second
Memory limit 128 MiB

Bessie has been given n segments on a 1D number line. The i-th segment contains all reals x such that l[i]xr[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 subsets of the given set of n segments, modulo 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 data

The first line contains n (1n10^5) and k (2k10). 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..2n.

Output data

Output the answer, modulo 10^9 + 7.

Example

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.

Examples

Input example #1
3 2
1 6
2 3
4 5
Output example #1
10
Source 2020 USACO February, Platinum