You are given a tree (a connected undirected graph without cycles) of n vertices. Each of the n - 1 edges of the tree is colored in either black or red.

You are also given an integer k. Consider sequences of k vertices. Let's call a sequence [a_1, a_2, …, a_k] good if it satisfies the following criterion:

  * We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from a_1 and ending at a_k. 
  * Start at a_1, then go to a_2 using the shortest path between a_1 and a_2, then go to a_3 in a similar way, and so on, until you travel the shortest path between a_{k-1} and a_k.
  * If you walked over at least one black edge during this process, then the sequence is good. 

<image>

Consider the tree on the picture. If k=3 then the following sequences are good: [1, 4, 7], [5, 5, 3] and [2, 3, 7]. The following sequences are not good: [1, 4, 6], [5, 5, 5], [3, 7, 3].

There are n^k sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 10^9+7.

Input

The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 100), the size of the tree and the length of the vertex sequence.

Each of the next n - 1 lines contains three integers u_i, v_i and x_i (1 ≤ u_i, v_i ≤ n, x_i ∈ \{0, 1\}), where u_i and v_i denote the endpoints of the corresponding edge and x_i is the color of this edge (0 denotes red edge and 1 denotes black edge).

Output

Print the number of good sequences modulo 10^9 + 7.

Examples

Input


4 4
1 2 1
2 3 1
3 4 1


Output


252

Input


4 6
1 2 0
1 3 0
1 4 0


Output


0

Input


3 5
1 2 1
2 3 0


Output


210

Note

In the first example, all sequences (4^4) of length 4 except the following are good: 

  * [1, 1, 1, 1]
  * [2, 2, 2, 2]
  * [3, 3, 3, 3]
  * [4, 4, 4, 4] 



In the second example, all edges are red, hence there aren't any good sequences.
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class C {
    private static int k;
    private static long count;
    private static long ans = 0;
    private static long cst = 1000000007;

    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();

        int[] tmp = scanner.nextIntArray();
        int n = tmp[0];
        k = tmp[1];

        Graph graph = new Graph(n);
        for (int i = 0; i < n - 1; i++) {
            int[] tmp2 = scanner.nextIntArray();
            if (tmp2[2] == 0) {
                graph.addEdge(tmp2[1] - 1, tmp2[0] - 1);
                graph.addEdge(tmp2[0] - 1, tmp2[1] - 1);
            }
        }

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            count = 0;
            if (!visited[i]) {
                dfs(i, visited, graph);
                ans += ((long)pow(count, k) - count) % cst;
            }
        }
        ans = ((long)pow(n, k) - ans - n) % cst;
        System.out.println(ans);
    }

    public static void dfs(int u, boolean[] visited, Graph g) {
        count++;
        visited[u] = true;
        for (Integer v : g.edge.get(u)) {
            if (!visited[v]) {
                dfs(v, visited, g);
            }
        }
    }

    private static class DisjointSet {
        int parent, rank;
        public DisjointSet() {
            parent = -1;
            rank = 0;
        }
        public DisjointSet(int i) {
            parent = i;
            rank = 0;
        }
    }

    private static class UnionFind {
        public static int find(DisjointSet[] ds, int i) {
            if (ds[i].parent != i)
                ds[i].parent = find(ds, ds[i].parent);
            return ds[i].parent;
        }
        public static void union(DisjointSet[] ds, int x, int y) {
            int xRoot = find(ds, x);
            int yRoot = find(ds, y);

            if (ds[xRoot].rank < ds[yRoot].rank) {
                ds[xRoot].parent = yRoot;
            } else if (ds[xRoot].rank > ds[yRoot].rank) {
                ds[yRoot].parent = xRoot;
            } else {
                ds[yRoot].parent = xRoot;
                ds[xRoot].rank++;
            }
        }
    }

    public static class Graph {
        ArrayList<ArrayList<Integer>> edge;
        public Graph(int v) {
            edge = new ArrayList <>();
            for (int i = 0; i < v; i++)
                edge.add(new ArrayList <>());
        }
        public void addEdge(int u, int v) {
            edge.get(u).add(v);
        }
    }
    private static class FastScanner {
        private BufferedReader br;

        public FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); }
        public int[] nextIntArray() throws IOException {
            String line = br.readLine();
            String[] strings = line.trim().split("\\s+");
            int[] array = new int[strings.length];
            for (int i = 0; i < array.length; i++)
                array[i] = Integer.parseInt(strings[i]);
            return array;
        }
    }
}
