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, [starti, endi], 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ța

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 1.000.000.009.

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, starti endi fi, unde [starti, endi] reprezintă intervalul de timp în care al i-lea copil este disponibil pentru a face parte din echipă, iar fi reprezintă piciorul cu care joacă al i-lea copil, fi =1 dacă al i-lea copil este dreptaci și fi =0 dacă al i-lea copil este stângaci.

Date de ieșire

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

Restricții și precizări

• 2 ≤ K ≤ N ≤ 100.000
• 0 ≤ starti ≤ endi ≤ 1.000.000.000, pentru orice i de la 0 la N − 1
• fi ∈ {0, 1}, pentru orice i de la 0 la N − 1
• Pentru 25 de puncte, K = 2 și 2 ≤ N ≤ 1000
• Pentru 17 de puncte, K = 2 și există cel mult 5 copii care sunt stângaci
• Pentru 33 de puncte, 2 ≤ K ≤ N ≤ 1000
• Pentru 25 de puncte, fără 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.