现在你面前有一棵n个节点的树（全连通无环图）。树上的边只有2种颜色，红色或者黑色。现在还给你一个整数k，考虑下面这个k个节点的序列[a1, a2, ..., ak]。 [a1, a2, ..., ak]如果是”好序列“当且仅当满足下面的条件： 1. 我们要走一条从a1开始到ak结束的路径。 2. 从a1开始，到a2走一条a1到a2的最短路。然后从a2开始，继续走一条到a3的最短路，以此类推，最终到a(k-1)和ak。 3. 走的路径中至少包含一条黑色的边。 我们看一下上面的图片中的树，如果k=3，那么下面的序列是“好序列”：[1,4,7], [5,5,3]。下面的序列不是好序列： [1,4,6], [5,5,5], [3,7,3]。 总共有n^k（n的k次方种路径方案），那么有多少路径是“好序列”呢？这个值可能非常大，输出的结果对(10^9+7)取模就可以。

输入描述:

第一行是2个整数n和k，其中(2 下面n-1行，每行包含3个整数，u[i], v[i], w[i]，其中1 = u[i], v[i] = n, w[i] = 0或1。u[i], v[i]表示这两个节点之间有一条边，w[i]表示这条边的颜色，其中0表示红色，1表示黑色。

输出描述:

输出所有“好序列”的个数模(10^9+7)