Najprv historické okienko: O Rímskej Ríši vieme rádovo dve veci:

1. Rímska Ríša pozostáva z $n$ miest označených číslami $1$ až $n$.
2. Medzi niektorými dvojicami miest vedie cesta.
3. Málokto to vie, ale známe porekadlo “všetky cesty vedú do Ríma” pochádza z faktu, že po týchto cestách sa dá z každého mesta Rímskej Ríše dostať do každého iného, ale aj z toho, že tieto cesty nikde netvoria cykly (teda, keď sa nad tým zamyslíte, vlastne to vylučuje existenciu nekonečných ciest, ktoré, očividne, nikam nevedú, teda ani do Ríma).
4. O Rímskej Ríši vieme rádovo dve veci.

Keď ste si toto všetko zapamätali, príbeh tejto úlohy vám už bude dávať zmysel:

Jedného krásneho dňa si plebejci povedali, že už toho majú dosť, a dnes je ten krásny deň, keď Cézarovi ukážu svoju novú zbierku multifunkčných kuchynských nožíkov, ktoré videli v teleshoppingu. Tak išli išli, po ľubovoľnej ceste (mohli si to dovoliť, pretože poznali príslovie o tom, že všetky cesty vedú do Ríma). Nakoniec do toho Ríma prišli, ale jój, beda prebeda! Brutus zabudol, že jeho vrecká sú ušité zo syra, a zbierka nožíkov sa vyrezala von a porozsýpala po celej Rímskej Ríši. Prvý nápad, ktorý plebejci mali, bol ako ľudia, ktorí majú rozum, nožíky proste pozbierať. Lenže tie sa zaborili do zeme čepeľou nahor, a teraz to vyzerá, že by bolelo vyberať ich von, tak sa to nikomu nechce robiť. Našťastie existuje ešte jedna prastará pranostika: Keď nejde hora k Mohamedovi, príde Mohamed k hore. Keď vykonáme substitúciu do tohto tvrdenia, zistíme, že Cézar môže prísť ku zbierke nožíkov. Tak plebejci vymysleli perfektný plán: založia s Cézarom kapelu, stanú sa slávnimi, a potom pôjdu na turné.

Teraz muzikologické okienko: O turné vieme rádovo tri veci:

1. Turné dĺžky $k$ je postupnosť $k$ čísel z rozsahu od $1$ po $n$ reprezentujúcich mestá Rímskej Ríše (posebeidúce čísla nemusia reprezentovať susedné mestá, a dokonca ani rôzne mestá, teda môžu byť rovnaké).
2. Dve turné sú rôzne práve vtedy, keď majú buď rôznu dĺžku, alebo na niektorom mieste majú rôzne čísla.
3. Málokto to vie, ale keď ide Cézar na turné, vyzerá to takto: najprv sa objaví za zvuku gitary a špeciálnych audiovizuálnych efektov v meste, ktoré je v postupnosti prvé. Následne sa vždy najkratšou možnou trasou po cestách Rímskej Ríše presunie do nasledovného mesta, a toto opakuje, až kým sa nedostane na koniec postupnosti.
4. O turné vieme rádovo dve veci.

Už je vám dúfam všetko jasné. Brutus navrhne Cézarovi turné, ten naň pôjde, a bum! Aspoň raz pôjde po ceste, v ktorej je nožík, a pokochá sa ním. Má to ale byť super tajné epické prekvapenie, a preto chce Brutus dať Cézarovi ilúziu výberu, aby si myslel, že má slobodnú vôľu. Preto potrebuje od vás vedieť jediné - počet všetkých rôznych turné danej dĺžky $k$, ktoré prechádzajú po aspoň jednej ceste s nožíkom. Zmodulovaný Cézarovym obľúbeným číslom, samozrejme.

Úloha

Poznáte $n$ miest v Rímskej Ríši, a $n-1$ ciest, ktoré spájajú niektoré mestá tak, aby boli všetky nejakou postupnosťou ciest spojené. O každej ceste okrem toho aj viete, či ide o hranu noža (teda či je na tejto ceste nožík).

Turné dĺžky $k$ je postupnosť $k$ miest. Mestá v postupnosti nemusia byť priamo spojené cestou. Dokonca môže to isté mesto byť v postupnosti viackrát za sebou.

Cézar si vždy najskôr vyberie turné dĺžky $k$ a následne sa medzi mestami vo zvolenom turné postupne presúva, vždy najkratšou možnou cestou.

Vašou úlohou je zistiť, koľko najviac rôznych turné dĺžky $k$ môžeme Cézarovi prezentovať, aby ho každé jedno z nich viedlo v nejakom bode po hrane noža.

Toto číslo môže byť veľmi veľké, preto odpoveď zmodulujte konštantou $10^9 + 7$.

Formát vstupu

Na prvom riadku sa nachádzajú čísla $n$ – počet miest a $k$ – dĺžka turné.

Nasleduje $n - 1$ riadkov. V každom z nich sa nachádzajú čísla $a$, $b$, $x$. Tieto čísla hovoria, že existuje cesta medzi mestami $a$ a $b$ a nožík sa na nej nachádza, ak $x = 1$, a nenachádza, ak $x = 0$.

Formát výstupu

Na výstup vypíšte jedno číslo – počet rôznych turné dĺžky $k$, počas ktorých Cézar prejde po aspoň jednej ceste s nožíkom, modulo $10^9 + 7$.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklad

5 4
1 3 0
2 3 0
3 4 1
4 5 0

528

3 3
1 2 0
3 2 0

0