Cây có cạnh đen

Cho một cây (đồ thị vô hướng liên thông không có chu trình) gồm $n$ đỉnh. Mỗi trong số $n-1$ cạnh của cây được tô màu đen hoặc đỏ.

Bạn được cho một số nguyên $k$. Xét các dãy gồm $k$ đỉnh. Một dãy $[a_1,a_2,\dots ,a_k]$ được gọi là tốt nếu nó thỏa mãn điều kiện sau:

• Ta đi một đường trên cây (có thể đi qua cùng một cạnh hoặc đỉnh nhiều lần), bắt đầu từ $a_1$ và kết thúc ở $a_k$: xuất phát từ $a_1$, đi đến $a_2$ theo đường đi ngắn nhất giữa $a_1$ và $a_2$, rồi đi đến $a_3$ theo cách tương tự, và cứ thế cho đến khi đi hết đường đi ngắn nhất giữa $a_{k-1}$ và $a_k$.
• Nếu trong quá trình đi ta đi qua ít nhất một cạnh màu đen, thì dãy đó là tốt.

Có tất cả $n^k$ dãy đỉnh. Hãy đếm xem có bao nhiêu dãy trong số đó là tốt. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ — kích thước cây và độ dài dãy đỉnh.
• Mỗi trong $n-1$ dòng tiếp theo chứa ba số nguyên $u_i$, $v_i$ và $x_i$, trong đó $u_i$ và $v_i$ là hai đầu mút của cạnh, còn $x_i$ là màu của cạnh ($0$ là cạnh đỏ, $1$ là cạnh đen).

Dữ liệu ra

In ra một số nguyên — số dãy tốt, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $2\le n\le {10}^5$
• $2\le k\le 100$
• $1\le u_i,v_i\le n$
• $x_i\in \{0,1\}$
• Các cạnh tạo thành một cây.

Ví dụ