E. Майк ба Геометрийн бодлого

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Майк ОУМО(Олон улсын математикийн олимпиад)-д бэлдэхийг хүссэн боловч тэрээр геометрийн тухай мэдэхгүй байв. Иймд түүний багш түүнд нэгэн сонирхолтой геометрийн бодлого өгчээ. $f([l, r]) = r - l + 1$ гэдгээр $[l, r]$ сегмент дээр байх бүхэл тоон цэгүүдийн тоог тэмдэглэв(энд $l ≤ r$ байх бөгөөд гэж үзнэ). Танд 2 бүхэл тоо $n$ болон $k$ мөн $OX$ тэнхлэг дээрх $n$ ширхэг хаалттай интервал $[l_{i}, r_{i}]$-ууд өгөгдсөн ба та дараах нийлбэрийн утгыг олох юм:

Өөрөөр хэлбэл та эдгээр өгөгдсөн сегментүүдийн аль ч $k$ ширхэг сегментүүдийнх нь огтлолцол дээрх бүхэл тоон цэгүүдийн тоонуудын нийлбэрийг олох юм.

Бодлогын хариулт хэтэрхий том тоо байж болох учраас хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодон хэвлэнэ үү.

Майк уг бодлогыг бодож чадахгүй байгаа тул түүнд таны тусламж хэрэг болжээ. Та түүнд тусална тийм үү?

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 200 000$) өгөгдөх ба эдгээр нь харгалзан сегментүүдийн тоо болон огтлолцлын хэсэгт байх сегментийн тоог илэрхийлнэ.

Дараа нь $n$ ширхэг мөр өгөгдөх ба эдгээрийн $i$-дахь мөрөнд 2 бүхэл тоо $l_{i}, r_{i}$ $( - 10^{9} ≤ l_{i} ≤ r_{i} ≤ 10^{9})$ өгөгдсөн байх бөгөөд эдгээр нь $i$-р сегментийн доод болон дээд хязгааруудыг илэрхийлнэ.

Гаралт

Майк-ын бодлогын хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодсон утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 2
1 2
1 3
2 3
Гаралт
5
Оролт
3 3
1 3
1 3
1 3
Гаралт
3
Оролт
3 1
1 2
2 3
3 4
Гаралт
6

Тэмдэглэл

Эхний жишээ:

;

;

.

Иймд хариулт нь $2 + 1 + 2 = 5$ байна.

Сэтгэгдлүүдийг ачааллаж байна...