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;
const int N = 1e6 + 5;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const int oo = 0x7fffffff;
const int sup = 0x80000000;
template <typename it>
void db(it *begin, it *end) {
  while (begin != end) cout << (*begin++) << " ";
  puts("");
}
template <typename it>
string to_str(it n) {
  string s = "";
  while (n) s += n % 10 + '0', n /= 10;
  reverse(s.begin(), s.end());
  return s;
}
template <typename it>
int o(it a) {
  cout << a << endl;
  return 0;
}
inline long long mul_64(long long x, long long y, long long c) {
  return (x * y - (long long)((long double)x / c * y) * c + c) % c;
}
inline long long ksm(long long a, long long b, long long c) {
  long long ans = 1;
  for (; b; b >>= 1, a = a * a % c)
    if (b & 1) ans = ans * a % c;
  return ans;
}
inline void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= x * (a / b);
}
int n, k;
int f[N], son[N];
int fa(int x) { return f[x] = x == f[x] ? x : fa(f[x]); }
int main() {
  for (int i = 1; i < N; i++) f[i] = i, son[i] = 1;
  cin >> n >> k;
  for (int i = 1; i < n; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    if (c == 1) continue;
    int fx = fa(u), fy = fa(v);
    if (fx ^ fy) {
      f[fx] = fy;
      son[fy] += son[fx];
    }
  }
  long long ans = (ksm(n, k, mod) - n + mod) % mod;
  for (int i = 1; i <= n; i++) {
    if (f[i] == i && son[i] > 1) {
      ans -= ksm(son[i], k, mod) - son[i];
      ans = (ans % mod + mod) % mod;
    }
  }
  printf("%lld\n", ans);
}
