Doprogramovanie do: 26. apríl 2024 23:59
3 dni
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

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\)\(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:

Sada 1 2 3 4
\(1 \leq n \leq\) \(20\) \(1000\) \(2 \cdot 10^5\) \(2 \cdot 10^5\)
\(1 \leq a_i \leq b_i \leq\) \(1\,000\) \(10^9\) \(100\) \(10^9\)

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.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.