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.
//package year2019.month03.cf.round548div2;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Objects;

public class round548div2C {

    boolean ONLINE_JUDGE = (System.getProperty("ONLINE_JUDGE") != null);

    public round548div2C() throws IOException {
        InputReader in;
        if (ONLINE_JUDGE) {
            in = new InputReader(System.in);
        } else {
            in = new InputReader(new FileInputStream("/Users/karj/cp/input.txt"));
        }
        PrintWriter out = new PrintWriter(System.out);

        int T = 1;
        for (int caseNo = 1; caseNo <= T; caseNo++) {
            solve(caseNo, in, out);
        }

        out.close();
    }

    long MOD = (long) (1e9 + 7);

    private void solve(int caseNo, InputReader in, PrintWriter out) throws IOException {
        int n = in.nextInt(), k = in.nextInt();
        LinkedList<Integer> g[] = new LinkedList[n];
        int c[] = new int[n - 1];
        for (int i = 0; i < n; i++) {
            g[i] = new LinkedList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1, v = in.nextInt() - 1, cc = in.nextInt();
            c[i] = cc;
            debug(u, v, cc);
            if (cc == 0) {
                g[u].addLast(v);
                g[v].addLast(u);
            }
        }
        debug(g);
        int ccc = 0;
        int ccs[] = new int[n + 1];
        boolean vis[]= new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ccc++;
                int cc = 0;
                dfs(i, cc, ccc, ccs, vis, g);
            }
        }
        debug(ccc, ccs);
        long ans = modPow(n, k, MOD);
        for (int i = 1; i <= ccc; i++) {
            long vv = modPow(ccs[i], k, MOD);
            vv %= MOD;
            ans -= vv;
            if (ans < 0) {
                ans += MOD;
            }
        }
        out.println(ans);
    }

    private int dfs(int u, int cc, int ccc, int[] ccs, boolean[] vis, LinkedList<Integer>[] g) {
        vis[u] = true;
        cc++;
        for (int v : g[u]) {
            if (!vis[v]) {
                int c = 0;
                cc += dfs(v, c, ccc, ccs, vis, g);
            }
        }
        ccs[ccc] = cc;
        return cc;
    }

    long modPow(long base, long exponent, long MOD) {
        long result = 1;
        base = base % MOD;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = result * base;
                result %= MOD;
            }
            exponent = exponent / 2;
            base = (base * base) % MOD;
        }
        return result;
    }

    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public interface SpaceCharFilter {

            public boolean isSpaceChar(int ch);
        }

        public String next() {
            return nextString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public Long nextLong() {
            return Long.parseLong(nextString());
        }

        public Double nextDouble() {
            return Double.parseDouble(nextString());
        }

        public char nextCharacter() {
            return nextString().charAt(0);
        }

        public int[] nextIntArray(int N) {
            int A[] = new int[N];
            for (int i = 0; i < N; i++) {
                A[i] = nextInt();
            }
            return A;
        }

        public long[] nextLongArray(int N) {
            long A[] = new long[N];
            for (int i = 0; i < N; i++) {
                A[i] = nextLong();
            }
            return A;
        }

        public double[] nextDoubleArray(int N) {
            double A[] = new double[N];
            for (int i = 0; i < N; i++) {
                A[i] = nextDouble();
            }
            return A;
        }
    }

    int min(int... a) {
        int min = Integer.MAX_VALUE;
        for (int v : a) {
            min = Math.min(min, v);
        }
        return min;
    }

    long min(long... a) {
        long min = Long.MAX_VALUE;
        for (long v : a) {
            min = Math.min(min, v);
        }
        return min;
    }

    double min(double... a) {
        double min = Double.MAX_VALUE;
        for (double v : a) {
            min = Math.min(min, v);
        }
        return min;
    }

    int max(int... a) {
        int max = Integer.MIN_VALUE;
        for (int v : a) {
            max = Math.max(max, v);
        }
        return max;
    }

    long max(long... a) {
        long max = Long.MIN_VALUE;
        for (long v : a) {
            max = Math.max(max, v);
        }
        return max;
    }

    double max(double... a) {
        double max = Double.MIN_VALUE;
        for (double v : a) {
            max = Math.max(max, v);
        }
        return max;
    }

    public <A, B> Pair MP(A a, B b) {
        return new Pair<A, B>(a, b);
    }

    class Pair<F, S> {
        public final F f;
        public final S s;

        public Pair(F f, S s) {
            this.f = f;
            this.s = s;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(f, pair.f) &&
                    Objects.equals(s, pair.s);
        }

        @Override
        public int hashCode() {

            return Objects.hash(f, s);
        }

        @Override
        public String toString() {
            return f.toString() + " " + s.toString();
        }
    }


    private void debug(Object... o) {
        if (ONLINE_JUDGE) {
            return;
        }
        System.err.println(Arrays.deepToString(o));
    }

    public static void main(String args[]) throws IOException {
        new round548div2C();
    }
}
