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 com.sun.org.apache.xpath.internal.operations.Mod;

import java.io.*;
import java.util.*;

public class Q2 {

    static int BFSList(ArrayList<Integer> graph[],int visit[],int m,int val){

        LinkedList<Integer> check=new LinkedList<>();
        check.add(m);
        visit[m]=1;
        val++;

        while(true){
            if(check.isEmpty())
                return val;
            int data=check.remove();
           // System.out.print(data+" ");

            for(int i=0;i<graph[data].size();i++){
                if(visit[graph[data].get(i)]==0) {
                    check.add(graph[data].get(i));
                    visit[graph[data].get(i)]=1;
                    val++;
                }
            }

        }

    }


    public static void main(String[] args) {

        InputReader in = new InputReader();
        int N = in.nextInt();

        ArrayList<Integer>[] input = new ArrayList[N+1];
        int k = in.nextInt();
        int mod=(int)1e9+7;

        for (int i = 1; i < N; i++) {
            int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
            if (input[a] == null)
                input[a] = new ArrayList<>();
            if (input[b] == null)
                input[b] = new ArrayList<>();

            if (c == 0) {
                input[a].add(b);
                input[b].add(a);
            }
        }

        long FinalAns=ModMultiIteBetter(N,k,mod);

        int visit[]=new int [N+1];


        int val;
        for(int i=1;i<=N;i++) {
            if(visit[i]==0){
                val=0;
              val=BFSList(input,visit,i,val);
              long tempAns=ModMultiIteBetter(val,k,mod);
              FinalAns=(FinalAns-tempAns+mod)%mod;
            }
        }
        long ans=(FinalAns )% mod;
        System.out.println(ans);

    }

    static long ModMultiIteBetter(int a, int b, int c) {

        if (b == 0)
            return 1;

        long sol = 1;

        while (b != 0) {
            int temp1 = b & 1;
            if (temp1 == 1)
                sol = (int) (((long) (a % c) * (sol % c)) % c);
            a = (int) ((((long) a % c) * (a % c)) % c);
            b = b / 2;
        }

        return sol;
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public int[] shuffle(int[] arr) {
            Random r = new Random();
            for (int i = 1, j; i < arr.length; i++) {
                j = r.nextInt(i);
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }
            return arr;
        }

        public InputReader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public char nextChar() {
            return next().charAt(0);
        }

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

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

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

        public int[] nextIntArr(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = this.nextInt();
            }
            return arr;
        }

        public Integer[] nextIntegerArr(int n) {
            Integer[] arr = new Integer[n];
            for (int i = 0; i < n; i++)
                arr[i] = new Integer(this.nextInt());

            return arr;
        }

        public int[][] next2DIntArr(int n, int m) {
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = this.nextInt();
                }
            }
            return arr;
        }

        public int[] nextSortedIntArr(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = this.nextInt();
            }
            Arrays.sort(arr);
            return arr;
        }

        public long[] nextLongArr(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = this.nextLong();
            }
            return arr;
        }

        public char[] nextCharArr(int n) {
            char[] arr = new char[n];
            for (int i = 0; i < n; i++) {
                arr[i] = this.nextChar();
            }
            return arr;
        }


        public static int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        public static int[] uwiSieve(int n) {
            if (n <= 32) {
                int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
                for (int i = 0; i < primes.length; i++) {
                    if (n < primes[i]) {
                        return Arrays.copyOf(primes, i);
                    }
                }
                return primes;
            }

            int u = n + 32;
            double lu = Math.log(u);
            int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
            ret[0] = 2;
            int pos = 1;

            int[] isp = new int[(n + 1) / 32 / 2 + 1];
            int sup = (n + 1) / 32 / 2 + 1;

            int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
            for (int tp : tprimes) {
                ret[pos++] = tp;
                int[] ptn = new int[tp];
                for (int i = (tp - 3) / 2; i < tp << 5; i += tp)
                    ptn[i >> 5] |= 1 << (i & 31);
                for (int i = 0; i < tp; i++) {
                    for (int j = i; j < sup; j += tp)
                        isp[j] |= ptn[i];
                }
            }

            // 3,5,7
            // 2x+3=n
            int[] magic = {0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21, 17,
                    9, 6, 16, 5, 15, 14};
            int h = n / 2;
            for (int i = 0; i < sup; i++) {
                for (int j = ~isp[i]; j != 0; j &= j - 1) {
                    int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
                    int p = 2 * pp + 3;
                    if (p > n)
                        break;
                    ret[pos++] = p;
                    for (int q = pp; q <= h; q += p)
                        isp[q >> 5] |= 1 << (q & 31);
                }
            }

            return Arrays.copyOf(ret, pos);
        }

        public static int[] radixSort(int[] f) {
            return radixSort(f, f.length);
        }

        public static int[] radixSort(int[] f, int n) {
            int[] to = new int[n];
            {
                int[] b = new int[65537];
                for (int i = 0; i < n; i++) b[1 + (f[i] & 0xffff)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < n; i++) to[b[f[i] & 0xffff]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            {
                int[] b = new int[65537];
                for (int i = 0; i < n; i++) b[1 + (f[i] >>> 16)]++;
                for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
                for (int i = 0; i < n; i++) to[b[f[i] >>> 16]++] = f[i];
                int[] d = f;
                f = to;
                to = d;
            }
            return f;
        }
    }
}
