== include(page="template/taskheader" task_id="taxi2") ==

Ne aflăm în anul $2050$, iar metroul din Drumul Taberei a fost inaugurat recent. Firmele de Taxi consideră că viaţa bucureştenilor a devenit acum prea bună, aşa că au hotărât să-i pedepsească mărind costurile unei călătorii cu taxi-ul. Mai exact, un client care face o comandă telefonică trebuie acum să plătească taxi-ul şi pentru distanţa pe care acesta o parcurge de la locaţia sa iniţială până la adresa clientului. Mai mult, dacă la un moment dat există $M$ comenzi telefonice care trebuie satisfăcute şi $M$ taximetrişti liberi, dispeceratul va cupla taximetriştii cu comenzile astfel încât distanţa totală parcursă de către cei $M$ taximetrişti să fie maximă. Noi dorim să studiem costurile unui asemenea cuplaj, în funcţie de poziţiile iniţiale ale taximetriştilor şi ale clienţilor.

Ne aflăm în anul $2050$, iar metroul din Drumul Taberei a fost inaugurat recent. Firmele de Taxi consideră că viaţa bucureştenilor a devenit acum prea bună, aşa că au hotărât să-i pedepsească mărind costurile unei călătorii cu taxi-ul. Mai exact, un client care face o comandă telefonică trebuie acum să plătească taxi-ul şi pentru distanţa pe care acesta o parcurge de la locaţia sa iniţială până la adresa clientului. Mai mult, dacă la un moment dat există $M$ comenzi telefonice care trebuie satisfăcute şi $M$ taximetrişti liberi, dispeceratul va cupla taximetriştii cu comenzile astfel încât distanţa totală parcursă de către cei $M$ taximetrişti până la adresele corespunzătoare să fie maximă. Noi dorim să studiem costurile unui asemenea cuplaj, în funcţie de poziţiile iniţiale ale taximetriştilor şi ale clienţilor.

Bucureştiul a devenit între timp un arbore neorientat cu $N$ noduri şi costuri muchii (o transformare tragică, dar care nu a înrăutăţit neaparat traficul). Fiecare dintre cei $M$ taximetrişti se poate afla în oricare din cele $N$ noduri. Acelaşi lucru este valabil pentru fiecare dintre cei $M$ clienţi. Un nod poate găzdui un număr nelimitat de taximetrişti şi/sau clienţi. Astfel, există în total $N^2M^$ configuraţii diferite ale poziţiilor taxi/client. Întrebarea noastră este următoarea: Dacă $S$ ar fi suma cuplajelor maxime pentru toate cele $N^2M^$ configuraţii, ce valoare ar avea $S *modulo* 10^9^ + 7$.