[USACO Feb 2020 G]Help Yourself
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Bessie has been given N (1≤N≤105) segments on a 1D number line. The ith segment contains all reals x such that li≤x≤ri.
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≤K≤10).

Bessie wants to compute the sum of the complexities over all 2N subsets of the given set of N segments, modulo 109+7.

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

输入描述:

The first line contains N and K.
Each of the next N lines contains two integers li and ri. It is guaranteed that li<ri and all li,ri are distinct integers in the range 1…2N.

输出描述:

Output the answer, modulo 109+7.
示例1

输入

复制
3 2
1 6
2 3
4 5

输出

复制
10

说明

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.

备注:

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