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!
SCORING
- 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).
INPUT FORMAT (file help.in):
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 FORMAT (file help.out):
Output the answer, modulo 109+7.SAMPLE INPUT:
3 2 1 6 2 3 4 5
SAMPLE OUTPUT:
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.
Problem credits: Benjamin Qi