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 sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


def get_int():
    return int(input())


def get_ints():
    return list(map(int, input().split(' ')))


def get_int_grid(n):
    return [get_ints() for _ in range(n)]


def get_str():
    return input().split(' ')


def yes_no(b):
    if b:
        return "YES"
    else:
        return "NO"


def binary_search(good, left, right, delta=1, right_true=False):
    """
    Performs binary search
    ----------
    Parameters
    ----------
    :param good: Function used to perform the binary search
    :param left: Starting value of left limit
    :param right: Starting value of the right limit
    :param delta: Margin of error, defaults value of 1 for integer binary search
    :param right_true: Boolean, for whether the right limit is the true invariant
    :return: Returns the most extremal value interval [left, right] which is good function evaluates to True,
            alternatively returns False if no such value found
    """

    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False


def prefix_sums(a, drop_zero=False):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    if drop_zero:
        return p[1:]
    else:
        return p


def prefix_mins(a, drop_zero=False):
    p = [float('inf')]
    for x in a:
        p.append(min(p[-1], x))
    if drop_zero:
        return p[1:]
    else:
        return p


def solve_a():
    n = get_int()
    s = get_str()
    cnt = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            cnt += i + 1
    return cnt


def solve_b():
    n = get_int()
    a = get_ints()
    curr = float('inf')
    S = 0
    while a:
        curr = max(0, min(curr - 1, a.pop()))
        S += curr
    return S


class DSU:

    # Disjoint Set Union (Union-Find) Data Structure
    def __init__(self, nodes, recursive=True, choose_join=True):
        # Parents
        self.p = [i for i in range(nodes)]
        # Ranks
        self.r = [0 for i in range(nodes)]
        # Sizes
        self.s = [1 for i in range(nodes)]
        self.recursive = recursive
        self.choose_join = choose_join

    def _get_recursive(self, u):
        if u != self.p[u]:
            self.p[u] = self.get(self.p[u])
        return self.p[u]

    def _get_nonrecursive(self, u):
        v = self.p[u]
        while v != self.p[v]:
            v = self.p[v]
        while u != v:
            u, self.p[u] = self.p[u], v
        return v

    def get(self, u):
        if self.recursive:
            return self._get_recursive(u)
        else:
            return self._get_nonrecursive(u)

    def union(self, u, v):
        # Unites the sets with identifiers u and v
        u = self.get(u)
        v = self.get(v)
        if u != v:
            if self.r[u] > self.r[v] and self.choose_join:
                u, v = v, u
            self.p[u] = v
            if self.r[u] == self.r[v]:
                self.r[v] += 1
            self.s[v] += self.s[u]


def solve_c():
    n, k = get_ints()
    M = 10 ** 9 + 7
    D = DSU(n)
    for _ in range(n - 1):
        u, v, x = get_ints()
        if x == 0:
            D.union(u - 1, v - 1)
    good = pow(n, k, M)
    for i in range(n):
        if D.get(i) == i:
            good -= pow(D.s[i], k, M)
            good %= M
    return good


print(solve_c())
