8. Ako priečinky robia radosť

Každý rok sa v T2 koná Každoročná Slávnosť Priečinkov (KSP). Vedúci púšťajú hity z entertainmenta, popíjajú kofolu a pun-ishujú sa tými najhoršími slovnými hračkami, aké ste kedy počuli.

Odovzdávajú si tiež priečinky! Konkrétne, vedúci ktorí majú v skrini vlastný priečinok ho niekedy prenechajú novému prvákovi. Priečinky sú veľmi praktické - môžu si v nich nechávať zošity do školy, materiály o najbližšom sústredení, pokazené routery, nedojedené desiaty…

Využitie priečinku sa však časom často mení. Niektorí ho v prváku naplnia vecami a potom naňho zabudnú. Iným príde najprv nepodstatný a až po rokoch zistia, že sa bez neho zrazu nezaobídu.

Z historických záznamov máš o mnoho vedúcich informácie o ich narábaním s priečinkami.

Presnejšie, o vedúcom číslo \(i\) vieš, že sa stal prvákom v roku \(p_i\) a priečinok využíval \(a_i\) veľa, zatiaľ čo ho už chcel odovzdať v roku \(o_i\) keď svoj priečinok využíval \(b_i\) veľa. Samozrejme, prenechal ho na KSP len takému prvákovi, ktorý by jeho priečinok využil ostro viac ako on.

Môže sa stať, že vedúci \(x\) odovzdá svoj priečinok prvákovi \(y\), ktorý neskôr odovzdá svoj priečinok prvákovi \(z\) a tak ďalej. Takúto sériu odovzdávaní nazveme životná púť priečinka. Keď vedúci \(x\) odovzdá priečinok vedúcemu \(y\), využitie priečinka stúpne o \(a_y - b_x\). Radosť, ktorú priečinok prináša vedúcemu, ktorý ho vlastní, je úmerná jeho využitu – preto túto hodnotu nazývame radosť odovzdávania. hodnota životnej púte priečinka je súčet radostí odovzdávania, ktoré počas tejto púte nastali.

Zo záznamov nie je jasné, kto komu priečinok naozaj aj odovzdal. Životné púte priečinkov sú tak stratené v histórií. Nič ti však nebráni upustiť uzdu fantázií, a predstaviť si tie najlepšie, najhodnotejšie púte, ktoré priečinky v T2 mohli zažiť. Keďže však musíme fantázií pokladať nejaké medze, predstavíš si len \(k\) najhodnotnejších z nich…

Úloha

Zistite, akých \(k\) najhodnotnejších životných pútí sa mohlo počas rokov KSP odohrať. Dve životné púte priečinka považujeme za rôzne, ak sú postupnosti vedúcich, ktorí ho vlastnili, iné.

Nemusíš nám ich detailne vypisovať. Stačí, ak vypíšeš súčet ich hodnôt modulo \(10^9+7\).

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(k\), udávajúce počet vedúcich, o ktorích máš záznam a počet najhodnotnejších životných pútí, ktoré ťa zaujímajú.

V \(i\)-tom z nasledujúcich \(n\) riadkov sú štyri čísla \(p_i\), \(o_i\), \(a_i\) a \(b_i\).

Platí \(1 \leq p_i < o_i \leq 10^9\), \(1 \leq a_i, b_i \leq 10^9\) a \(1 \leq n \cdot k \leq 10^6\).

V jednotlivých sadách platia nasledujúce obmedzenia pre \(n\) a \(k\):

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - súčet hodnôt \(k\) najhodnotnejších životných pútí, ktoré mohli počas rokov KSP nastať, modulo \(10^9+7\). Ak ich mohlo nastať menej ako \(k\), vypíš súčet všetkých z nich (stále modulo \(10^9+7\)).

Príklady

Input:

5 1
1 2 10 9
1 4 7 11
2 4 15 16
4 5 20 1
5 7 2 5

Output:

11

Najhodnotnejšia možná životná púť priečinka je, aby prvý vedúci odovzdal priečinok tretiemu, ten potom štvrtému a ten nakoniec piatemu.

Input:

5 4
1 2 10 9
1 4 7 11
2 4 15 16
4 5 20 1
5 7 2 5

Output:

40

Druhá a tretia najhodnotnejšia púť sú prvý-tretí-štvrtý, druhý-štvrtý-piaty s hodnotou 10. Štvrtá najhodnotnejšia púť, s hodnotou 9, je druhý-štvrtý

Input:

3 1
1 1000000 1 1
1000000 50000000 1000000000 1
50000000 1000000000 1000000000 474747

Output:

999999991

Najhodnotejšia púť je prvý-druhý-tretí s hodnotou \((1000000000-1)+(1000000000-1)=1999999998\), modulo \(10^9+7 = 999999991\)

Input:

10 1
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

Output:

10

Input:

10 5
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

Output:

45

Input:

10 25
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

Output:

113

Existuje len 22 životných pútí, sčítame teda všetky