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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class edgy {
	
	static class Node {
		int data;
		Node link;
		
		Node(int d,Node l){
			data=d;
			link=l;
		}
	}

	
	static class queue {
		protected Node front;
		protected Node rear;
		int size;
		
		queue(){
			front=null;
			rear=null;
			size=0;
		}
		
		boolean isEmpty() {
			return rear==null;
		}
		
		void enqueue(int x) {
			Node nptr=new Node(x,null);
			if(rear==null) {
				front=nptr;
			}
			else {
				rear.link=nptr;
			}
			rear=nptr;
			size++;
		}
		
		int dequeue() {
			int n=front.data;
			front=front.link;
			if(front==null) {
				rear=null;
			}
			size--;
			return n; 
		}
		
		int see() {
			int n=front.data;
			return n;
		}
		
	}

	
	static class gedgy{
		
		int n;
		ArrayList<ArrayList<Integer>> adj;
		
		gedgy(int V) {
			n=V;
			adj=new ArrayList<ArrayList<Integer>>();

			for(int i=0;i<n;i++) {
				adj.add(new ArrayList<Integer>());
			}
		}
		
		void add_edge(gedgy g,int a,int b){
		
			g.adj.get(a).add(b);
			g.adj.get(b).add(a); // **IMP** ONLY IF THE GRAPH IS UNDIRECTED

		}
		
		long BFS(gedgy g,int s,int[] visit) {
			queue q=new queue();						
			
			//int inf=-1;
			q.enqueue(s);
			visit[s]=1;
			//visit[s]=count;
			
			long count=1;
			
			while(!q.isEmpty()) {
				int v=q.dequeue();
				
				for(int w : g.adj.get(v)) {
						
						if(visit[w]==0) {
							visit[w]=1;
							count+=1;
							q.enqueue(w);
						}
					
				}
			}
			return count;
		}


	}



	/** Class for buffered reading int and double values */
	static class Redgy {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		/** call this method to initialize reader for InputStream */
		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		/** get next word */
		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				// TODO add check for eof if necessary
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}

		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		
		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}

	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Redgy.init(System.in);
		
		int n=Redgy.nextInt();
		int k=Redgy.nextInt();
		
		gedgy g=new gedgy(n);
		
		for(int i=0;i<n-1;i++) {
			int u=Redgy.nextInt();
			int v=Redgy.nextInt();
			int x=Redgy.nextInt();
			
			if(x==0) {
				g.add_edge(g, u-1, v-1);
			}
		}
		
		int[] visit=new int[n];
		
		long ans=(long)Math.pow((double)n, (double)k)%1000000007;
		
		for(int e=0;e<visit.length;e++) {
			if(visit[e]==0) {
				double c=g.BFS(g, e, visit);
				
				ans=ans-(long)Math.pow(c, k)%1000000007;
			}
		}
		
		System.out.println(ans);
	}

}

