7. Nečakaný výlet

Peder sedel pri počítači a nadšene si sťahoval nový diel svojho obľúbeného seriálu Fraiser na svojej obľúbenej stránke uloz-stiahni-to-zadarmo-free-serialy-filmy.tv

Zrazu na neho však vyskočila dáka ruleta a nápis
\(\\\) DOBRÝ DEŇ, STE DNEŠNÝM ŠŤASTNÝM VÍŤAZOM NAŠEJ ANKETY
Každý týždeň odmeňujeme piatich účastníkov našej ankety cenami hodnoty až 10000 EUR.
\(\\\) (Peder žiadnu anketu nevypĺňal…)

Peder, samozrejme ako každý normálny človek ruletu roztočil, a čo to nevidí? Získava hlavnú cenu: \(k+1\) lístkov do Legolandu! Jeden si nechá určite pre seba. Ale čo s ostatnými?

Úloha

Peder má \(n\) kamarátov. \(i\)-ty z nich má voľno v dňoch \(a_i\) až \(b_i\) vrátane. Spočítajte, koľkými spôsobmi vie vybrať \(k\) z nich tak, že všetci majú aspoň jeden spoločný voľný deň.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet Pederových kamarátov a \(k\) (\(1 \leq k \leq n\)) – počet lístkov, ktoré má pre kamarátov. Na každom z nasledujúcich \(n\) riadkov sa nachádzajú dve celé čísla \(a_i\) a \(b_i\) – interval voľného času \(i\)-teho kamaráta.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo – počet spôsobov, ako prideliť kamarátom lístky. Keďže toto číslo môže byť veľmi veľké, vypíšte len jeho zvyšok po delení \(10^9 + 7\).

Príklad

Input:

3 3
1 4
2 3
2 8

Output:

1

\(k=n\), čiže Peder potrebuje zobrať všetkých kamarátov. I keď má dva možné termíny, kedy ich môže zobrať, stále je to tá istá skupina a tak je odpoveď \(1\).

Input:

3 2
1 4
4 9
6 14

Output:

2

Môže zobrať buď prvého a druhého alebo druhého a tretieho.