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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;

public class Main {

    /**
     * 并查集
     *
     * @author hemenghai
     * @date 2019-02-24
     */
    private static class Dsu {

        private int[] ancient;
        private int[] count;

        public Dsu(int size){
            ancient = new int[size];
            count = new int[size];
            for (int i = 0; i < size; i++) {
                ancient[i] = i;
                count[i] = 1;
            }
        }

        /**
         * 寻找祖先节点
         */
        public int root(int x){
            while (x != ancient[x]){
                x = ancient[x];
            }
            return x;
        }

        /**
         * 是否为根节点
         */
        public boolean isRoot(int x){
            return x == ancient[x];
        }
        
        /**
         * 获取集合成员个数
         */
        public int count(int x){
            while (x != ancient[x]){
                x = ancient[x];
            }
            return count[x];
        }

        /**
         * 合并族群
         */
        public void union(int a, int b){
            int ra = root(a);
            int rb = root(b);

            if(ra!=rb){
                ancient[ra] = rb;
                count[rb] = count[rb] + count[ra];
            }
        }
    }

    private static final long MODULE = 1_000_000_000 + 7;

    private static long cur, pos, sum, len;
    private static long max, min, ans, res;
    private static int ai, bi, ci, di;
    private static int[] aix, bix;
    private static int[][] aixx, bixx;
    private static long al, bl, cl, dl;
    private static long[] alx, blx;
    private static long[][] alxx, blxx;
    private static double ad, bd, cd, dd;
    private static double[] adx, bdx;
    private static double[][] adxx, bdxx;
    private static boolean ab, bb, cb, db;
    private static boolean[] abx, bbx;
    private static boolean[][] abxx, bbxx;
    private static char ac, bc, cc, dc;
    private static char[] acx, bcx;
    private static char[][] acxx, bcxx;
    private static String as, bs, cs, ds;
    private static InputReader in = new InputReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int n = in.nextInt();
        int k = in.nextInt();

        Dsu dsu = new Dsu(n);
        
        int a, b, tag;
        for (int i = 1; i < n; i++) {
            a = in.nextInt() - 1;
            b = in.nextInt() - 1;
            tag = in.nextInt();
            if(tag == 0){
                dsu.union(a, b);
            }
        }

        for (int i = 0; i < n; i++) {
            if(dsu.isRoot(i)){
                sum = (sum + powerMod(dsu.count(i), k, MODULE)) % MODULE;
            }
        }
        ans = (powerMod(n, k, MODULE) + MODULE - sum) % MODULE;
        out.println(ans);
        out.close();
    }


    private static long  powerMod(long  x, long  n, long  module) {
        // 特判
        if(module == 1){
            return 0;
        }
        long sum = 1;
        x = x % module;
        while (n > 0) {
            if (n % 2 == 1) {
                //判断是否是奇数，是奇数的话将多出来的数事先乘如sum
                sum = (sum * x) % module;
            }
            n >>= 1;
            // 不断的两两合并再取模，减小a和b的规模
            x = (x * x) % module;
        }
        return sum;
    }

    private static class InputReader {

        private InputStream stream;

        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

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

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

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

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

        private 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++];
        }
    }
}