fotbal

Cei $N$ copii de la școala generală vor să formeze o echipă de fotbal compusă din $K$ elevi, dintre care cel puțin unul stângaci și cel puțin unul dreptaci. Pentru fiecare copil $i$ (de la $0$ la $N-1$) se cunoaște intervalul de timp în care acesta este disponibil pentru a face parte din echipă, sub forma unei perechi, $[start_{i}, end_{i}]$, cât și dacă este stângaci sau dreptaci. $K$ copii pot juca în aceeași echipa dacă intervalele de timp în care aceștia sunt disponibili se suprapun în cel puțin un punct (moment de timp).

Cerință

Se cere numărul de moduri în care se poate alcătui o echipă cu $K$ dintre cei $N$ elevi; deoarece acest număr poate să fie foarte mare, el se va afișa modulo $10^9+9$.

Date de intrare

Pe prima linie din fișierul fotbal.in se găsesc numerele $N$ și $K$. Pe următoarele $N$ linii, se găsesc câte 3 numere naturale, $start_{i}$, $end_{i}$, $f_{i}$, unde $[start_{i}, end_{i}]$ reprezintă intervalul de timp în care al $i$-lea copil este disponibil pentru a face parte din echipă, iar $f_{i}$ reprezintă piciorul cu care joacă al $i$-lea copil, $f_{i}=1$ dacă al $i$-lea copil este dreptaci și $f_{i}=0$ dacă al $i$-lea copil este stângaci.

Date de ieșire

Fișierul fotbal.out va conține doar numărul de moduri cerut, în forma precizată în cerință.

Restricții și precizări

• $2 \leq K \leq N \leq 100 \ 000$;
• $0 \leq start_{i} \leq end_{i} \leq 1 \ 000 \ 000 \ 000$, pentru orice $i$ de la $0$ la $N-1$;
• $f_{i} \in \{0, 1\}$, pentru orice $i$ de la $0$ la $N-1$;
• Pentru $25$ de puncte, $K = 2$ și $2 \le N \le 1 \ 000$;
• Pentru $17$ puncte, $K = 2$ și există cel mult $5$ copii care sunt stângaci;
• Pentru $33$ de puncte, $2 \leq K \leq N \leq 1 \ 000$;
• Pentru $25$ de puncte, nu există restricții suplimentare.

Exemplu

fotbal.in

5 2
1 8 0
2 5 1
3 7 0
0 9 1
6 12 0

fotbal.out

5

Explicație

Posibilele echipe sunt $(0, 1)$, $(0, 3)$, $(1, 2)$, $(2, 3)$, $(3, 4)$. Nu putem forma, de exemplu, echipa $(2, 4)$ deoarece ambii copii sunt stângaci. Totodată, nu putem forma echipa $(1, 4)$, deoarece intervalele de timp în care cei doi copii sunt disponibili nu se suprapun în niciun punct.