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.*;
public class Main {
    static int time=0;
    static int count=0;
    public static void main(String args[])
    {
        FastReader input=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        int T=1;
        while(T-->0)
        {
            int n=input.nextInt();
            int k=input.nextInt();
            ArrayList<Pair> adj[]=new ArrayList[n+1];
            for(int i=1;i<=n;i++)
            {
                adj[i]=new ArrayList<>();
            }
            for(int i=0;i<n-1;i++)
            {
                int u=input.nextInt();
                int v=input.nextInt();
                int x=input.nextInt();
                adj[u].add(new Pair(v,x));
                adj[v].add(new Pair(u,x));
            }
            ArrayList<Integer> list=dfs(adj);
            long m=1000000007;
            long sum=0;
            long s=0;
            for(int i=0;i<list.size();i++)
            {
                int v=list.get(i);
                s+=v;
                long p=power(v,k,m);
                sum=(sum%m+p%m)%m;
            }
            long rem=n-s;
            sum=(sum%m+rem%m)%m;
            long total=power(n,k,m);
            long ans=(total%m-sum%m)%m;
            if(ans<0)
            {
                ans+=m;
            }
            out.println(ans);
        }
        out.close();
    }
    public static long power(long a,long b,long m)
    {
        long res=1;
        while(b>0)
        {
            if(b%2!=0)
            {
                res=(res%m*a%m)%m;
            }
            b=b/2;
            a=(a%m*a%m)%m;
        }
        return res;
    }
    public static ArrayList<Integer> dfs(ArrayList<Pair> adj[])
    {
        int n=adj.length;
        Vertex V[]=new Vertex[n];
        for(int i=1;i<n;i++)
        {
            V[i]=new Vertex(i);
        }
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<n;i++)
        {
            if(V[i].color=="white")
            {
                count=0;
                dfsVisit(adj,V,i);
                if(count>1)
                {
                    list.add(count);
                }
            }
        }
        return list;
    }
    public static void dfsVisit(ArrayList<Pair> adj[],Vertex V[], int u)
    {
        time++;
        V[u].color="gray";
        V[u].d=time;
        count++;
        for(int i=0;i<adj[u].size();i++)
        {
            int v=adj[u].get(i).v;
            if (V[v].color=="white" && adj[u].get(i).x==0)
            {
                V[v].parent=V[u];
                dfsVisit(adj,V,v);
            }
        }
        time++;
        V[u].f=time;
        V[u].color="black";
    }
    public static class Vertex
    {
        int key;
        int d,f;
        String color;
        Vertex parent;
        Vertex(int key)
        {
            this.key=key;
            this.d=0;
            this.f=0;
            this.color="white";
            this.parent=null;
        }
    }
    static class Pair
    {
        int v,x;
        Pair(int v,int x)
        {
            this.v=v;
            this.x=x;
        }
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        long nextLong()
        {
            return Long.parseLong(next());
        }
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}