5. Iba aby hladný nebol

Neďaleho hovniválovho bytu je park, v ktorom je síce dosť chodníkov na to, aby sa dalo dostať z každého na každý, ale netvoria žiaden cyklus. Hovniválovi sa teda určite nestane, že by chodil dokola mysliac si, že už o chvíľu určite príde na chodník s lahodnou pochutinou.

Taký park by ale bez neporiadnych psíčkarov vôbec nebol lákavý. Kde-tu sa vyskytne mäkká, hnedastá kôpka maškrty. Jednoducho raj pre hovniválov. Ten náš má vymyslenú vynikajúcu stratégiu. Každú križovatku chodníkov si očísloval. Vždy, keď ide do parku zháňať niečo pod zub, rozhodne sa, ktorých \(k\) križovatiek postupne navštívi. Tieto križovatky nemusia byť priamo spojené chodníkom. Medzi dvoma križovatkami sa vždy presúva najkratšou možnou cestou. Ako tak kráča po chodníkoch, dúfa, že aspoň na jednom z nich nájde voňavú pochúťku.

Hovnivála by zaujímalo, koľko rôznych prechádzok, na ktorých nájde aspoň nejakú tú podslinku, si vie naplánovať.

Úloha

Poznáte popis parku. O každej z \(n\) križovatiek viete, ktoré z čísel od \(1\) do \(n\) jej hovnivál priradil. Každé dve križovatky majú rôzne čísla.

Križovatky sú rôzne pospájané chodníkmi. Chodníkov je \(n - 1\) a platí, že sa po nich dá dostať z každej križovatky do každej inej.

Na každom chodníku sa buď nachádza, alebo nenachádza exkrement.

Prechádzka dĺžky \(k\) je postupnosť \(k\) križovatiek. Križovatky v postupnosti nemusia byť priamo spojené hranou. Dokonca môže tá istá križovatka byť v postupnosti viackrát za sebou.

Hovnivál si vždy najskôr vyberie prechádzku dĺžky \(k\) a následne sa medzi križovatkami vo zvolenej prechádzke presúva najkratšou možnou cestou.

Vašou úlohou je zistiť, koľko rôznych prechádzok dĺžky \(k\) si môže hovnivál zvoliť, aby pre každú z nich platilo, že počas nej prejde po aspoň jednom chodníku s exkrementom.

Formát vstupu

Na prvom riadku sa nachádzajú čísla \(n\) – počet križovatiek a \(k\) – dĺžka prechádzky.

Nasleduje \(n - 1\) riadkov. V každom z nich sa nachádzajú čísla \(a\), \(b\), \(x\). Tieto čísla hovoria, že existuje chodník medzi križovatkami \(a\) a \(b\) a exkrement sa na ňom 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 prechádzok dĺžky \(k\), počas ktorých hovnivál prejde po aspoň jednom chodníku s exkrementom modulo \(10^9 + 7\).

Hodnotenie

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

Príklad

Input:

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

Output:

528

Vhodnými prechádzkami sú tu napríklad [1, 5, 3, 2], alebo [3, 3, 5, 3]. Nevhodnou je napríklad [1, 3, 2, 1].

Input:

3 3
1 2 0
3 2 0

Output:

0

Žiadna prechádzka nevyužíva chodník s exkrementom, pretože v celom parku žiadny taký chodník nie je.