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