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.util.*;
import java.math.*;

// **** C. Edgy Trees ****

public class C {
	static char [] in = new char [10000];
	static int [] stack = new int [100001];
	static long MOD = 1000000007L;
	static class AL extends ArrayList<Integer>{ 
		public AL (int n) { super(n);}
	};
	public static void main (String [] arg) throws Throwable {
		int n = nextInt();
		int k = nextInt();
		AL [] graphB = new AL[n];
		AL [] graphR = new AL[n];
		for (int i = 0; i<n-1; ++i) {
			int u = nextInt()-1;
			int v = nextInt()-1;
			int x = nextInt();
			if (x == 1) {
				add(graphB, u, v);
			} else {
				add(graphR, u, v);
			}
		}
		boolean [] visR = new boolean [n];
		boolean [] visB = new boolean [n];
		long ans = ntothek(n,k);
		
		for (int i = 0; i<n; ++i) {
			long TMP1 = CountConnected(graphR, visR, i);
			//long TMP2 = CountConnected(graphB, visB, i);
			//System.err.println(i + " : " + TMP1 + " red  and " + TMP2 + " black");
			ans -= ntothek(TMP1, k);
			//ans -= ntothek(TMP2, k);
			//ans++; //Doublecount iiiiiiii
		}
		System.out.println(ans);
	}
	public static long CountConnected(AL[] graph, boolean [] vis, int start) {
		if (vis[start]) return 0;
		if (graph[start] == null) return 1;
		
		int stackptr = 1;
		int curptr = 0;
		stack[0] = start;
		long ans = 0;
		while (curptr < stackptr) {
			int cur = stack[curptr];
			vis[cur] = true;
			for (int i = 0; i<graph[cur].size(); ++i) {
				int v = graph[cur].get(i);
				if (!vis[v]) {
					stack[stackptr] = v;
					stackptr++;
					vis[v] = true;
				}
			}
			curptr++;
		}
		return stackptr;
	}
	
	
	public static long ntothek(long n, long k) {
		long ans = 1L;
		for (int i = 0; i<k; ++i) ans = (ans * n) % MOD;
		return ans;
	}
	public static void add(AL[] graph, int u, int v) {
			if (graph[u] == null) graph[u] = new AL(10);
			if (graph[v] == null) graph[v] = new AL(10);
			graph[u].add(v);
			graph[v].add(u);
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 45) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 42 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 42) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
}

/* Full Problem Text:
  
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.
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.

 */