Bessie has been given \(N\) (\(1\le N\le 10^5\)) segments on a 1D number line. The
\(i\)th segment contains all reals \(x\) such that \(l_i\le x\le 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\) (\(2\le K\le 10\)).

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!

Problem credits: Benjamin Qi

SCORING

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

Problem credits: Benjamin Qi

The first line contains \(N\) and \(K\).

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 \ldots 2N.\)

Output the answer, modulo \(10^9+7\).

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > February > Platinum