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.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x = x * f;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename E>
E gcd(E a, E b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename E>
E lcm(E a, E b) {
  return a * b / gcd(a, b);
}
template <typename E>
E ex_gcd(E a, E b, E &x, E &y) {
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
template <typename E>
E quick_mul(E a, E b, E c) {
  E ans = 0;
  while (b) {
    if (b & 1) ans = (ans + a) % c;
    a = (a + a) % c;
    b >>= 1;
  }
  return ans;
}
template <typename E>
E quick_pow(E a, E b, E c) {
  E ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
template <typename E>
E inv1(E a, E b) {
  return quick_pow(a, b - 2, b);
}
template <typename E>
E inv2(E a, E b) {
  E x, y;
  ex_gcd(a, b, x, y);
  return (x % b + b) % b;
}
const double eps = 1.0e-5;
const int maxn = 200000 + 10;
const long long mod = 1e9 + 7;
int n, k, u, v;
vector<int> vec[maxn];
int r[maxn], b[maxn], l1 = 0, l2 = 0, c;
int fa[maxn], fa1[maxn], num[maxn], num1[maxn];
long long ans = 0;
int fin(int cur) { return fa[cur] == cur ? cur : (fa[cur] = fin(fa[cur])); }
int fin1(int cur) {
  return fa1[cur] == cur ? cur : (fa1[cur] = fin1(fa1[cur]));
}
void unite(int u, int v, int c) {
  if (c == 1) {
    int x = fin(u), y = fin(v);
    if (x != y) fa[x] = y;
  } else {
    int x = fin1(u), y = fin1(v);
    if (x != y) fa1[x] = y;
  }
}
struct node {
  int u, v, c;
} e[maxn];
bool cmp(node a, node b) { return a.c < b.c; }
int x, y, co[maxn];
bool flag[maxn];
int main() {
  scanf("%d %d", &n, &k);
  for (int i = (1); i <= (n); i++) fa[i] = fa1[i] = i;
  for (int i = (1); i <= (n - 1); i++) {
    scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].c);
  }
  int sta;
  sort(e + 1, e + n, cmp);
  for (int i = 1; i < n && e[i].c == 0; i++) {
    unite(e[i].u, e[i].v, 0);
    sta = i;
    co[e[i].u] = co[e[i].v] = 1;
  }
  long long cnt = 0;
  for (int i = sta + 1; i < n; i++) {
    if (!co[e[i].u]) {
      cnt++;
      co[e[i].u] = 1;
    }
    if (!co[e[i].v]) {
      cnt++;
      co[e[i].v] = 1;
    }
  }
  for (int i = (1); i <= (n); i++) {
    num1[fin1(i)]++;
  }
  for (int i = (1); i <= (n); i++) {
    if (num1[i] > 1) r[++l2] = num1[i];
  }
  ans = quick_pow((long long)n, (long long)k, mod) - cnt;
  for (int i = (1); i <= (l2); i++) {
    ans = (ans - quick_pow((long long)r[i], (long long)k, mod)) % mod;
  }
  printf("%lld\n", ((ans % mod) + mod) % mod);
}
