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, \ldots, 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 \le n \le 10^5$, $2 \le k \le 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 \le u_i, v_i \le n$, $x_i \in \{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.

Difficulty: interview

Starter code:

Solutions:
rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))
MOD = 10**9 + 7

class DSU:
    def __init__(self, N):
        #R * C is the source, and isn't a grid square
        self.par = list(range(N+1))
        self.rnk = [0] * (N+1)
        self.sz = [1] * (N+1)

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr: return
        if self.rnk[xr] < self.rnk[yr]:
            xr, yr = yr, xr
        if self.rnk[xr] == self.rnk[yr]:
            self.rnk[xr] += 1

        self.par[yr] = xr
        self.sz[xr] += self.sz[yr]

    def size(self, x):
        return self.sz[self.find(x)]
        
def solve(N, K, edges):
    graph = [[] for _ in range(N)]
    dsu = DSU(N)
    for u,v,w in edges:
        u-=1;v-=1
        if w==0: #red
            dsu.union(u, v)

    ans = pow(N, K, MOD)
    for x in range(N):
        if dsu.find(x) == x:
            ans -= pow(dsu.size(x), K, MOD)
            ans %= MOD
    return ans

for tc in range(1):#rri()):
    N, K = rrm()
    edges = [rrm() for _ in range(N-1)]
    print(solve(N, K, edges))


import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
EDGE=[list(map(int,input().split())) for i in range(n-1)]
mod=10**9+7

Group=[i for i in range(n+1)]
def find(x):
    while Group[x] != x:
        x=Group[x]
    return x
def Union(x,y):
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

for x,y,c in EDGE:
    if c==0:
        Union(x,y)

G=[find(i) for i in range(1,n+1)]

from collections import Counter
counter=Counter(G)

ANS=0
for j in list(counter.values()):
    ANS=(ANS+pow(j,k,mod))%mod

print((pow(n,k,mod)-ANS)%mod)


n, k = [int(i) for i in input().split()]
adj = [[] for i in range(n+1)]

ans = 0
# no of good paths = all paths - non-good paths
# = all paths - paths where no blacks

par = [i for i in range(n+1)]

def find(i):
    nonlocal par
    if par[i] == i:
        return i
    par[i] = find(par[i])
    return par[i]

def unite(i, j):
    nonlocal par
    if find(i) < find(j):
        i, j = j, i
    par[find(i)] = find(j)

for i in range(n-1):
    u, v, c = [int(i) for i in input().split()]
    adj[u].append((v,c))
    adj[v].append((u, c))
    if c==0:
        unite(u, v)

sz = [0 for i in range(n+1)]
for i in range(1, n+1):
    sz[find(i)] += 1
grps = []
for i in range(1, n+1):
    if find(i) == i:
        grps.append(i)
        
mod = 10**9 + 7
ans += pow(n, k, mod) #n**k

for i in grps:
    ans -= pow(sz[i], k, mod) #sz[i]**k
    ans += mod
print(ans%mod)


import collections

p = 10 ** 9 + 7

n, k = list(map(int, input().split()))

# g: List[List[int]]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b, x = list(map(int, input().split()))
    if x != 0:
        continue
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

v = [False] * n

bad = 0

for i in range(n):
    if v[i]:
        continue

    d = collections.deque()
    d.append(i)
    v[i] = True
    c = 0
    while d:
        i = d.pop()
        for j in g[i]:
            if v[j]:
                continue
            v[j] = True
            d.append(j)
        c += 1
    bad += pow(c, k, p)

print((pow(n, k, p) + p - bad) % p)


import sys
input = sys.stdin.readline
from collections import defaultdict

n, k = list(map(int, input().split()))
g = defaultdict(list)
for _ in range(n-1):
    u, v, x = list(map(int, input().split()))
    u, v = u-1, v-1
    if not x:
        g[u].append(v)
        g[v].append(u)
MOD = 10**9 + 7

res = pow(n, k, MOD)

visited = [False for _ in range(n)]
for i in range(n):
    if not visited[i]:
        cnt = 1
        visited[i] = True
        stack = [i]
        while stack:
            curr = stack.pop()
            for ne in g[curr]:
                if not visited[ne]:
                    visited[ne] = True
                    cnt += 1
                    stack.append(ne)
        res -= pow(cnt, k, MOD)

print(res % MOD)


import collections

class UnionFind:
    """Weighted quick-union with path compression.
    The original Java implementation is introduced at
    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
    >>> uf = UnionFind(10)
    >>> for (p, q) in [(3, 4), (4, 9), (8, 0), (2, 3), (5, 6), (5, 9),
    ...                (7, 3), (4, 8), (6, 1)]:
    ...     uf.union(p, q)
    >>> uf._id
    [8, 3, 3, 3, 3, 3, 3, 3, 3, 3]
    >>> uf.find(0, 1)
    True
    >>> uf._id
    [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
    """

    def __init__(self, n):
        self._id = list(range(n))
        self._sz = [1] * n

    def _root(self, i):
        j = i
        while (j != self._id[j]):
            self._id[j] = self._id[self._id[j]]
            j = self._id[j]
        return j

    def find(self, p, q):
        return self._root(p) == self._root(q)
    
    def union(self, p, q):
        i = self._root(p)
        j = self._root(q)
        if i == j:
            return
        if (self._sz[i] < self._sz[j]):
            self._id[i] = j
            self._sz[j] += self._sz[i]
        else:
            self._id[j] = i
            self._sz[i] += self._sz[j]

n, k = map(int, input().split())

uf = UnionFind(n)

for i in range(n-1):
    u, v, x = map(int, input().split())
    u -= 1
    v -= 1
    if x==0:
        uf.union(u, v)

d = collections.defaultdict(int)
for i in range(n):
    d[uf._root(i)] += 1

total = pow(n, k, 10**9+7)
for size in d.values():
    total -= pow(size, k, 10**9+7)

total %= 10**9+7

print(total)

n,k=list(map(int,input().split()))
g=[[] for _ in range(n+1)]

for i in range(n-1):
    u,v,c=list(map(int,input().split()))
    if c==0:
        g[u].append(v)
        g[v].append(u)
mod=10**9+7
def cal_pow(a,b):
    nonlocal mod
    i=0
    val=1
    while i<b:
        val=(val*a)%mod
        i+=1
    return (val-a+mod)%mod

summ=cal_pow(n,k)
vis=[False for _ in range(n+1)]
from collections import deque
def bfs(ind):
    q=deque()
    q.append(ind)
    cnt=0
    vis[ind]=True
    while q:
        indx=q.popleft()
        cnt+=1
        for v in g[indx]:
            if not vis[v]:
                q.append(v)
                vis[v]=True
    return cnt

for v in range(1,n+1):
    if not vis[v]:
        cnt=bfs(v)
        summ=((mod+summ)-(cal_pow(cnt,k)))%mod
print(summ)



n,k = map(int, input().split())
g = [[] for i in range(n)]
for i in range(n-1):
    u,v,x = map(int, input().split())
    g[u-1].append((v-1, x))
    g[v - 1].append((u - 1, x))

v = [0 for i in range(n)]
comps = []
for i in range(n):
    if v[i] == 1:
        continue
    v[i] = 1
    comps.append([i])
    q = [i]
    while q:
        u0 = q[0]
        q = q[1:]
        for u, x in g[u0]:
            if x == 0 and v[u] == 0:
                q.append(u)
                v[u] = 1
                comps[-1].append(u)

ans = n**k

for comp in comps:
    ans -= len(comp)**k
print(ans%((10**9) + 7))

# -*- coding: utf-8 -*-
# @Time    : 2019/3/21 23:56
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Edgy Trees.py


class UnionFind(object):
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.root[x] == x:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.root[y] = x
        self.size[x] += self.size[y]


def pow_mod(a, b, p):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % p
        b //= 2
        a = a * a % p
    return ret


def main():
    n, k = list(map(int, input().split()))

    union_find = UnionFind(n + 1)
    for _ in range(n - 1):
        u, v, c = list(map(int, input().split()))
        if c == 0:
            union_find.union(u, v)

    p = int(1e9 + 7)
    ret = pow_mod(n, k, p)
    used = set()
    for i in range(1, n + 1):
        x = union_find.find(i)
        if x not in used:
            ret = (ret + p - pow_mod(union_find.size[x], k, p)) % p
            used.add(x)
    print(ret)


def __starting_point():
    main()
    # print(pow_mod(4, 4, 3))

__starting_point()

MOD = 1000000007
n, k = list(map(int, input().split()))
ch = [set() for _ in range(n + 1)]
for _2 in range(n - 1):
    u, v, x = list(map(int, input().split()))
    if x == 0:
        ch[u].add(v)
        ch[v].add(u)
res = 0
root = [True] * (n + 1)
for i in range(1, n + 1):
    if root[i]:
        cur = 1
        stack = [i]
        while stack:
            u = stack.pop()
            for v in ch[u]:
                ch[v].remove(u)
                cur += 1
                root[v] = False
                stack.append(v)
        res = (res + pow(cur, k)) % MOD
res = (MOD + pow(n, k) - res) % MOD
print(res)


from collections import defaultdict as dd
mod= pow(10,9)+7
"""
def dfs_visit(V,adj,s,c):
    for v in adj[s]:
        if v not in parent:
            parent[v]=s
            c=c+1
            dfs_visit(V,adj,v,c)
    return(c)
            
def dfs(V,adj):
    ans=[]
    for s in V:
        if s not in parent:
            parent[s]=None
            c=dfs_visit(V,adj,s,1)
            ans.append(c)
    return(ans)
"""
def bfs(s,adj):
    nonlocal parent
    t=1
    #print("df",s)
    frontier=[s]
    while frontier:
        nex=[]
        for u in frontier:
            for v in adj[u]:
                if v not in parent:
                    #print(v)
                    t+=1
                    parent.add(v)
                    nex.append(v)
        frontier=nex
    return(t)

adj=dd(list)
n,k=[int(i) for i in input().split(' ')]
for ii in range(n-1):
    x,y,h=[int(i) for i in input().split(' ')]
    if h==0:
        adj[x].append(y)
        adj[y].append(x)

V=[i+1 for i in range(n)]  
parent=set()

fk=[]
for i in V:
    if i not in parent:
        parent.add(i)
        tr=bfs(i,adj)
        #print(i,tr)
        fk.append(tr)
#print(fk)
ans=pow(n,k,mod)
for i in fk:
    ans=(ans-pow(i,k,mod))%mod
print(ans%mod)


def factorial(n):
    if n == 0:
        return 1
    else:
        return (n * factorial(n-1))%(10**9+7)



n, k = [int(i) for i  in input().split()]
s = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = [int(i) for i in input().split()]
    if c == 0:
        s[a-1].append(b-1)
        s[b - 1].append(a - 1)
used = [False]*n

ans = pow(n, k, 10**9+7)
for i in range(n):
    if not used[i]:
        comp = []
        used[i] = True
        comp.append(i)
        c=0
        while c < len(comp):
            for h in s[comp[c]]:
                if not used[h]:
                    used[h] = True
                    comp.append(h)
            c+=1
        ans = (ans-pow(len(comp), k, 10**9+7))%(10**9+7)
print(ans)

from collections import defaultdict,deque
MOD = (10**9)+7
def bfs(v):
    q.append(v)
    visited[v]=True
    while q:
        s=q.popleft()
        b.append(v)
        for i in g[s]:
            if not visited[i[0]] and i[1]==0:
                q.append(i[0])
                visited[i[0]]=True
    
n,k=list(map(int,input().split()))
g=defaultdict(list)
for _ in range(n-1):
    x,y,c=list(map(int,input().split()))
    g[x].append((y,c))
    g[y].append((x,c))
visited=[False]*(n+1)
count=0;ans=pow(n,k,MOD)
q=deque()
for i in range(1,n+1):
    b=[]
    if visited[i]==False:
        bfs(i)
    #print(b)
    f =len(b) 
    count=(count+pow(f,k,MOD))%MOD

ans=(ans-count)%MOD
print(ans)



from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

import threading
threading.stack_size(67108864)
 
def main():
    n, k = list(map(int, input().split()))
    uw = []
    ubw = []
    for i in range(n):
        uw.append([])
        ubw.append([])
    for i in range(n - 1):
        a, b, v = list(map(int, input().split()))
        ubw[a - 1].append(b - 1)
        ubw[b - 1].append(a - 1)
        if v == 0:
            uw[a - 1].append(b - 1)
            uw[b - 1].append(a - 1)
    def dfs(v):
        use[v] = 1
        com[c] += 1
        for i in uw[v]:
            if not use[i]:
                dfs(i)
    use = [0] * n
    c = 0
    com = []
    for i in range(n):
        if not use[i]:
            com.append(0)
            dfs(i)
            c += 1
    q = 10 ** 9 + 7
    ans = pow(n, k, q)
    for i in range(c):
        ans -= pow(com[i], k, q)
        ans %= q
    print(ans)
thread = threading.Thread(target=main)
thread.start()
thread.join()



from collections import deque
mod = 10**9 + 7


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.edges = {}

    def add_edge(self, node, color):
        self.edges[node] = color


n, k = list(map(int, input().split()))
tree = []
for i in range(1, n+1):
    tree.append(TreeNode(i))

for _ in range(n-1):
    u, v, x = list(map(int, input().split()))
    tree[u-1].add_edge(v, x)
    tree[v-1].add_edge(u, x)

visited = set()
total = 0

for node in range(1, n+1):
    if node in visited:
        continue

    queue = deque()
    queue.append(node)
    visited.add(node)
    red_vertexes = 1
    while queue:

        vertex = queue.popleft()

        for (e, c) in list(tree[vertex-1].edges.items()):
            if c == 0 and e not in visited:
                queue.append(e)
                red_vertexes = red_vertexes + 1
                visited.add(e)

    total = (total + pow(red_vertexes, k, mod)) % mod

total = (pow(n, k, mod) - total) % mod
print(total)


N, k = map(int, input().split())
MOD = 10 ** 9 + 7
gr = [-1] * N
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if c == 0:
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

g = 0
for i in range(N):
    if gr[i] == -1:
        que = [i]
        while que:
            j = que.pop()
            gr[j] = g
            for w in G[j]:
                if gr[w] == -1:
                    que.append(w)
        g += 1

num = 0
ans = (N ** k) % MOD
d = [0] * N
for i in range(N):
    if gr[i] != -1:
        d[gr[i]] += 1

for i in range(N):
    num += d[i] ** k
    num %= MOD

print((ans - num + MOD) % MOD)