시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 22 8 7 33.333%

문제

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

N 이하의 정수 k가 주어질 때, \( \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개의 선분의 교집합의 길이의 합을 구하여야 합니다.

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

입력

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

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

출력

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

예제 입력 1

3 2
1 2
1 3
2 3

예제 출력 1

5

힌트

\( {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} \)