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.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package learning;

/**
 *
 * @author hp
 */
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Math1 {
    static long mod=(long)1e9+7;
    
    static int n = (int)1e8;
    static boolean[] prime;
    public static void main(String[] args)
    {
        //Scanner sc = new Scanner(System.in);
           InputReader sc = new InputReader(System.in);
         PrintWriter w = new PrintWriter(System.out);
  

        long x = sc.nl();
        long k = sc.nl();
        int c = 0;
        boolean []v  =new boolean[(int)x+1];
        for(int i=0;i<x-1;i++)
        {
            int a  =sc.ni();
            int b = sc.ni();
            int c1 = sc.ni();
            if(c1==0)
            {
               // c++;
                v[a] = true;
                v[b] = true;
            }
        }
        int p = 0;
        long res = modexp(x,k,mod);
        for(int i=1;i<=x;i++)
        {
            if(!v[i])
                p++;
        }
        c = p;
        p = (int)x-c;
   long res1 = modexp((long)p,k,mod);
   long res3 = (res - res1 - c + mod)%mod;
   //w.println(res1);
   w.println(res3);
        
         
         w.close();
           
       
    }
    static void newsieve() {
			Arrays.fill(prime	, true);
			prime[0] = prime[1] = false;
			for(int i = 2 ; i * i <= n ; ++i) {
				if(prime[i]) {
					for(int k = i * i; k< n ; k+=i) {
						prime[k] = false;
					}
				}
			}
			
		}
    
    static long phi(long nx)
    {
        // Initialize result as n
        double result = nx; 
        long temp = 0;
     
        // Consider all prime factors of n and for 
        // every prime factor p, multiply result
        // with (1 - 1/p)
        for (long p = 2; p * p <= nx; ++p)
        {
            // Check if p is a prime factor.
            if (nx % p == 0)
            {
                // If yes, then update n and result
                while (nx % p == 0)
                    nx /= p;
                result *= (1.0 - (1.0 / (double) p));
            }
        }
     
        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (nx > 1)
            result *= (1.0 - (1.0 / (double) nx));
     
        return (long)result;
    
    }
    
    static boolean[] seive(int n)
    {
        boolean []isp = new boolean[n+1];
        for(int i=2;i<=n;i++)
        {
            isp[i] = true;
        }
        for(int i=2;i*i<=n;i++)
        {
            if(isp[i])
            {
                for(int j=i*i;j<=n;j+=i)
                {
                    isp[j] = false;
                }
            }
        }
        return isp;
    }
    static int countDivisors(int n)
    {
        int cnt = 0;
        for (int i = 1; i*i <=n; i++)
        {
             if (n % i == 0)
             {
                // If divisors are equal,
                // count only one
                if (n / i == i)
                   cnt++;
      
                else // Otherwise count both
                    cnt = cnt + 2;
             }
         }
        return cnt;
    }
    
    static long modexp(long x,long n,long M)
{
    long power = n;
    long result=1;
    while(power>0)
    {
        if(power % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        power = power/2;
    }
    return result;
}
    static int nCr(int n, int r, int p)
{
    // The array C is going to store last row of
    // pascal triangle at the end. And last entry
    // of last row is nCr
    int []C = new int[r+1];
    Arrays.fill(C, 0);
 
    C[0] = 1; // Top row of Pascal Triangle
 
    // One by constructs remaining rows of Pascal
    // Triangle from top to bottom
    for (int i = 1; i <= n; i++)
    {
        // Fill entries of current row using previous
        // row values
        for (int j = Math.min(i, r); j > 0; j--)
 
            // nCj = (n-1)Cj + (n-1)C(j-1);
            C[j] = (C[j] + C[j-1])%p;
    }
    return C[r];
}
 
// Lucas Theorem based function that returns nCr % p
// This function works like decimal to binary conversion
// recursive function.  First we compute last digits of
// n and r in base p, then recur for remaining digits

    
    
    
    
    static int gcd(int a, int b)
    {
	 if (a == 0)
	  return b;
				         
	return gcd(b%a, a);
    }
    
    static int lcm(int a, int b)
    {
	 return (a*b)/gcd(a, b);
    }
    static int digitsum(int x)
    
    {    

        int sum = 0;
        while(x > 0)
        {
            int temp = x % 10;
            sum += temp;
            x /= 10;
        }
        return sum;
        
    }
    static int d = 0;
    static int x = 0;
    static int y = 0;
    
static void extendedEuclid(int A, int B)
{
    
    if(B == 0) {
        d = A;
        x = 1;
        y = 0;
    }
    else {
        extendedEuclid(B, A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
    
}
 static long modInverse(long A,long M)
{
    return modexp(A,M-2,M);
}
 
 public static boolean returnPrime(BigInteger number) {
    //check via BigInteger.isProbablePrime(certainty)
    if (!number.isProbablePrime(5))
        return false;

    //check if even
    BigInteger two = new BigInteger("2");
    if (!two.equals(number) && BigInteger.ZERO.equals(number.mod(two)))
        return false;

    //find divisor if any from 3 to 'number'
    for (BigInteger i = new BigInteger("3"); i.multiply(i).compareTo(number) < 1; i = i.add(two)) { //start from 3, 5, etc. the odd number, and look for a divisor if any
        if (BigInteger.ZERO.equals(number.mod(i))) //check if 'i' is divisor of 'number'
            return false;
    }
    return true;
}
 public static long lcm_of_array_elements(int[] element_array)
    {
        long lcm_of_array_elements = 1;
        int divisor = 2;
        while (true)
        {
            int counter = 0;
            boolean divisible = false;
            for (int i = 0; i < element_array.length; i++)
            {
                 
                 // lcm_of_array_elements (n1,n2,... 0) = 0.
                 // For negative number we convert into
                 // positive and calculate lcm_of_array_elements.
                 
                if (element_array[i] == 0)
                {
                    return 0;
                }
                else if (element_array[i] < 0)
                {
                    element_array[i] = element_array[i] * (-1);
                }
                if (element_array[i] == 1)
                {
                    counter++;
                }
                 
                 // divide element_array by devisor if complete division i.e. without
                 // remainder then replace number with quotient; used for find
                 // next factor
                 
                if (element_array[i] % divisor == 0)
                {
                    divisible = true;
                    element_array[i] = element_array[i] / divisor;
                }
            }
            
             // If divisor able to completely divide any number from array
             // multiply with lcm_of_array_elements and store into lcm_of_array_elements 
             // and continue to same divisor
             // for next factor finding. else increment divisor
              
            if (divisible)
            {
                lcm_of_array_elements = lcm_of_array_elements * divisor;
            }
            else
            {
                divisor++;
            }
         
             // Check if all element_array is 1 indicate we found all factors and
             // terminate while loop.
  
            if (counter == element_array.length)
            {
                return lcm_of_array_elements;
            }
        }
    }     
    // Function to find gcd of array of
    // numbers
    static int findGCD(int arr[], int n)
    {
        int result = arr[0];
        for (int i=1; i<n; i++)
            result = gcd(arr[i], result);
         
        return result;
    }
     static class InputReader {
 
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
 
		public InputReader(InputStream st) {
			this.stream = st;
		}
 
		public int read() {
			if (snumChars == -1)
	 			throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int ni() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nl() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nia(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = ni();
			}
			return a;
		}
 
		public String rs() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}
	

	
	
	
   
		static PrintWriter w = new PrintWriter(System.out);
 static char [][]sol;
    
    
    
}
