A Árvore

Seja uma árvore um grafo conexo sem ciclos que contém $n$ vértices. Você ganha de presente uma árvore especial. Nesta árvore, as $n-1$ arestas estão coloridas ou em preto
ou em vermelho.

Você ainda recebeu um inteiro $k$ de presente! Considere todas as sequências de $k$ vértices. Vamos chamar uma sequência $[a_1, a_2, ..., a_k]$ boa se ela satisfaz os seguintes critérios:

Nós vamos percorrer um caminho nesta árvore, começando em $a_1$ e finalizando em $a_k$ .
Começe em $a_1$ , então vá para $a_2$ utilizando o menor caminho entre $a_1$ e $a_2$ , depois vá para $a_3$ pela mesma maneira, e assim por diante, até você percorrer o menor caminho entre $a_{k-1}$ e $a_k$ .
Se você percorreu pelo menos uma aresta preta nesse processeo, então essa sequência é boa.

Existem $n^k$ sequências de vértices, conte quantos deles são bons. Como esse número pode ser muito grande, imprima-o módulo $10^9 + 7$ .

Entrada

A primeira linha contém dois inteiros $n$ e $k$ $(2\leq n\leq 10^5, 2\leq k\leq 100)$ , o tamanho da árvore e o comprimento da sequência de vértices.

Cada uma das $n-1$ linhas contém três inteiros $u_i$ , $v_i$ e $x_i$ $(1\leq u_i, v_i \leq n, x_i$ ∈ $\{ 0,1\} )$ , onde $u_i$ e $v_i$ são os vértices de tal aresta e $x_i$ é a cor desta aresta ( $0$ representa uma aresta vermelha e $1$ representa uma aresta preta).