QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 1994. Help Yourself

Statistics

Bessie has been given N (1N105) segments on a 1D number line. The ith segment contains all reals x such that lixri.

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 (2K10).

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 N16.
  • Test cases 3-5 satisfy N1000, K=2.
  • Test cases 6-8 satisfy N1000.
  • For each T[9,16], test case T satisfies K=3+(T9).

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 12N.

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