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.util.*;
public class sol {
    static long mod=(long)Math.pow(10,9)+7;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Integer> tree[];
    static boolean vis[];
    static int ar[];
    static int cnt=0;
    static void dfs(int x) {
        vis[x] = true;
        cnt++;
        for(Integer i : tree[x]) {
            if(!vis[i])
                dfs(i);
        }
    }
    public static void main(String args[])throws Exception {
        FastReader in = new FastReader(System.in); 
        int t=1,i,j;
        while(t-->0) { 
            int n = in.nextInt(),k=in.nextInt();
            tree = new ArrayList[n];
            vis = new boolean[n];
            for(i=0;i<n;i++)
                tree[i] = new ArrayList<>();
            for(i=1;i<n;i++) {
                int x = in.nextInt()-1,y = in.nextInt()-1,z=in.nextInt();
                if(z==0) {
                    tree[x].add(y);
                    tree[y].add(x);
                }
            }
            long ans=0,res=power(n,k);
            for(i=0;i<n;i++) {
                if(!vis[i]) {
                    cnt=0;
                    dfs(i);
                    ans=ans%mod + power(cnt,k);
                }
            }
            System.out.println((res-ans)%mod);
        }
    }
    static long power(long a,long b) {
        long res=1;
        a = a % mod;  
        while (b > 0) { 
            if((b & 1)==1) 
                res = (res * a) % mod;
            b = b >> 1;  
            a = (a * a) % mod;  
        } 
        return res; 
    }
    static void prt(int a[]) {
        for(int i=0;i<=a.length;i++)
            System.out.print(a[i]+" ");
        System.out.println();
    }
    static class Pair { 
        int a; 
        int b;  
        Pair(int x, int y) { 
            a = x; 
            b = y; 
        } 
    }
}
class FastReader {
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
    FastReader(InputStream is) {
        in = is;
    }
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}
/*static void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1; 
    int n2 = r - m; 
    int L[] = new int [n1]; 
    int R[] = new int [n2]; 
    for (int i=0; i<n1; ++i) 
        L[i] = arr[l + i]; 
    for (int j=0; j<n2; ++j) 
        R[j] = arr[m + 1+ j]; 
    int i = 0, j = 0; 
    int k = l; 
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } 
        else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
}  
static void sort(int arr[], int l, int r) { 
    if (l < r) {
        int m = (l+r)/2; 
        sort(arr, l, m); 
        sort(arr , m+1, r); 
        merge(arr, l, m, r); 
    } 
} */
/*static int gcd(int a, int b) { 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
}*/