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.