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).

Saída

Imprima o número de sequências boas módulo $$10^9 + 7$$.

Exemplo de Entrada 1

Exemplo de Saída 1

Exemplo de Entrada 2

Exemplo de Saída 2

Exemplo de Entrada 3

Exemplo de Saída 3