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.*;
import java.util.LinkedList;
/*
        author : Aditya Aggarwal

        LinkedIn : https://www.linkedin.com/in/aditya7861/

        ' The Dawn does not come twice to awaken the man '  ---->>>  ( My Motivation )

        Believe In yourself, Everything is possible.

        Never Give Up ... Failure is the biggest success
 */

public class Main
{

    static class AdityaFastIO
    {
        final private int BUFFER_SIZE = 1 << 16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        BufferedReader br;
        StringTokenizer st;

        public AdityaFastIO()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public AdityaFastIO(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        String word()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String line()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int ni() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nl() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nd() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }

    static int MOD = (int) (1e9 + 7);

    static long powerLL(long x, long n)
    {
        long result = 1;
        while (n > 0)
        {
            if (n % 2 == 1)
            {
                result = result * x % MOD;
            }
            n = n / 2;
            x = x * x % MOD;
        }
        return result;
    }

    static long powerStrings(String sa, String sb)
    {
        long a = 0, b = 0;

        for (int i = 0; i < sa.length(); i++)
        {
            a = (a * 10 + (sa.charAt(i) - '0')) %
                    MOD;
        }

        for (int i = 0; i < sb.length(); i++)
        {
            b = (b * 10 + (sb.charAt(i) - '0')) %
                    (MOD - 1);
        }

        return powerLL(a, b);
    }

    static long gcd(long a, long b)
    {
        if (a==0) return b;
        else return gcd(b%a,a);
    }

    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a,b);
    }

    static long lower_bound(List<Long> list, long k)
    {
        int s = 0;
        int e = list.size();

        while (s!=e)
        {
            int mid = (s+e)>>1;

            if (list.get(mid)<k) s = mid+1;
            else e = mid;
        }

        if (s == list.size()) return -1;
        return s;
    }

    static int upper_bound(List<Long> list, long k)
    {
        int s = 0;
        int e = list.size();

        while (s!=e)
        {
            int mid = (s+e)>>1;

            if (list.get(mid)<=k) s = mid+1;
            else e = mid;
        }

        if (s == list.size()) return -1;
        return s;
    }

    static void addEdge(ArrayList<ArrayList<Integer>>graph, int edge1, int edge2)
    {
        graph.get(edge1).add(edge2);
        graph.get(edge2).add(edge1);
    }

    static class Pair<X,Y>
    {
        public X first;
        public Y second;

        Pair(X first, Y second)
        {
            this.first = first;
            this.second = second;
        }

        public static <X,Y> Pair <X,Y> of (X a, Y b)
        {
            return new Pair<>(a,b);
        }

        public String toString()
        {
            return "("+first+","+second+")";
        }
    }

    static boolean isCollectionsSorted(List<Integer> list)
    {
        if (list.size() == 0 || list.size() == 1) return true;

        for (int i=1;i<list.size();i++) if (list.get(i)>list.get(i-1)) return false;

        return true;
    }

    static class Node
    {
        int key;
        Node left,right;

        Node(int key)
        {
            this.key = key;
        }
    }

    static int count = 0;
    static void BFS(ArrayList<ArrayList<Integer>> graph, int source, boolean[] visited)
    {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);

        //boolean[] visited = new boolean[graph.size()];
        visited[source] = true;

        while (!queue.isEmpty())
        {
            int v = queue.poll();
           // count++;

            for (int ele : graph.get(v))
            {
                if (!visited[ele])
                {
                    visited[ele] = true;
                    queue.add(ele);
                    count++;
                }
            }
        }
    }

    static void DFS(ArrayList<ArrayList<Integer>> graph, int source, boolean[] visited)
    {
        visited[source] = true;

        count++;

        for (int v : graph.get(source)) if (!visited[v]) DFS(graph, v, visited);
    }

    public static void main(String[] args) throws java.lang.Exception
    {
        try
        {
            AdityaFastIO r = new AdityaFastIO();

            try (OutputStream out = new BufferedOutputStream(System.out))
            {

                boolean tc = false;

                int testcases = tc?r.ni():1;

                while (testcases -- > 0)
                {
                    int n = r.ni(), k = r.ni();

                    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
                    for (int i=0;i<n+1;i++) graph.add(new ArrayList<>());

                    for (int i=0;i<n-1;i++)
                    {
                        int v1 = r.ni(), v2 = r.ni(), color = r.ni();

                        if (color!=1) addEdge(graph, v1, v2);
                    }

                    long ans = (long)Math.pow(n,k);

                    boolean[] visited = new boolean[n+1];
                    for (int i=1;i<=n;i++)
                    {
                        if (!visited[i])
                        {
                            count = 0;

                            //BFS(graph,i,visited);

                            DFS(graph, i, visited);

                            ans-=powerStrings(String.valueOf(count),String.valueOf(k))%MOD;
                        }
                    }

                    out.write((ans+"").getBytes());
                }
            }
        }
        catch(Exception e){}
        finally{}
    }
}
				 	  			 	 		  			 	 	  			