12992번 - 홍준이의 교집합

홍준이에게는 수평면 상에서 N개의 1차원 구간이 있습니다. i번째 구간을 [L_i , R_i](L_i ≤ R_i)라고 하겠습니다. 이때, 구간의 길이는 f([L_i , R_i])= R_i – L_i + 1로 정의하겠습니다. F(공집합) = 0입니다.

N 이하의 정수 k가 주어질 때, \( \displaystyle\sum_{1 \le i_1  < i_2  <  ...  < i_k  \le N} {f([L_{i_1}, R_{i_1}]\bigcap[L_{i_2}, R_{i_2}]\bigcap ... \bigcap [L_{i_k}, R_{i_k}])} \) 를 계산하는 프로그램을 작성하세요. 즉, 가능한 모든 서로 다른 k개의 선분을 골랐을 때 k개의 선분의 교집합의 길이의 합을 구하여야 합니다.

답이 매우 커질 수 있으므로, 10⁹+7로 나눈 나머지를 출력하세요.

첫째 줄에 N과 k가 주어집니다.(1 ≤ k ≤ N ≤ 200,000)

둘째 줄부터 N개의 줄에 걸쳐서 i+1(1 ≤ i ≤ N)번째 줄에 L_i와 R_i를 나타내는 2개의 정수가 주어집니다. (-10⁹ ≤ L_i, R_i ≤ 10⁹)

가능한 모든 서로 다른 k개의 선분을 골랐을 때 k개의 선분의 교집합의 길이의 합을 10⁹+7로 나눈 나머지를 출력하세요.

\( {f([1,2]\bigcap[1,3]) = f([1,2]) = 2} \)

\( {f([1,2]\bigcap[2,3]) = f([2,2]) = 1} \)

\( {f([1,3]\bigcap[2,3]) = f([2,3]) = 2} \)