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.io.*;
import java.util.*;

public class C {
    static class DSU {
        private final int n;
        private final int[] root;
        final int[] size;

        DSU(int n) {
            this.n = n;
            root = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                root[i] = i;
            }
            size = new int[n + 1];
            Arrays.fill(size, 1);
        }

        int findRoot(int x) {
            if (root[x] == x) {
                return x;
            }
            return root[x] = findRoot(root[x]);
        }

        void unite(int x, int y) {
            x = findRoot(x);
            y = findRoot(y);
            if (x != y) {
                root[x] = y;
                size[y] += size[x];
            }
        }
    }

    static class ModularArithmetic {
        private final int module;

        public ModularArithmetic(int module) {
            this.module = module;
        }

        public ModularArithmetic() {
            this(1_000_000_007);
        }

        final int sum(int a, int b) {
            int sum = a + b;
            return sum >= module ? sum - module : sum;
        }

        final int difference(int a, int b) {
            return sum(a, module - b);
        }

        final int product(int a, int b) {
            return (int)((long)a * b % module);
        }

        final int power(int x, int k) {
            int result = 1;
            while (k > 0) {
                if (k % 2 == 1) {
                    result = product(result, x);
                }
                x = product(x, x);
                k /= 2;
            }
            return result;
        }

        final int inverse(int x) {
            return power(x, module - 2);
        }
    }

    public static void main(String[] args) throws IOException {
        try (Input input = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            int n = input.nextInt();
            int k = input.nextInt();
            DSU dsu = new DSU(n);
            for (int i = 1; i < n; i++) {
                int u = input.nextInt();
                int v = input.nextInt();
                int color = input.nextInt();
                if (color == 0) {
                    dsu.unite(u, v);
                }
            }
            ModularArithmetic modular = new ModularArithmetic();
            int answer = modular.power(n, k);
            for (int i = 1; i <= n; i++) {
                if (dsu.findRoot(i) == i) {
                    answer = modular.difference(answer, modular.power(dsu.size[i], k));
                }
            }
            writer.println(answer);
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}