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 long long MOD = 1000000007ll;
const int INTMAX = numeric_limits<int>::max();
const long long LLMAX = numeric_limits<long long>::max();
void writeln() { cout << "\n"; }
template <class T>
inline void print(T&& a);
template <class T>
inline void priws(T&& a);
template <class T>
inline void read(T& a);
template <class... Args>
inline void readln(Args&... args) {
  (read(args), ...);
}
template <class H, class... T>
inline void writeln(H&& h, T&&... t) {
  priws(h);
  (print(t), ...);
  writeln();
}
template <class T>
inline void writeln_range(T f, T s) {
  if (f != s)
    for (auto i = f; i != s; ++i) writeln(*i);
}
vector<string> split(string& s, string d) {
  vector<string> v;
  size_t p = 0;
  while ((p = s.find(d)) != string::npos)
    v.push_back(s.substr(0, p)), s.erase(0, p + d.length());
  v.push_back(s);
  return v;
}
template <class... Args>
inline void err(string v, Args... args) {
  auto vv = split(v, ", ");
  auto it = vv.begin();
  (writeln(*it++, "=", args), ...);
}
template <typename T>
T binpowmod(T a, long long n, T mod) {
  assert(n > 0);
  T res = a;
  --n;
  while (n > 0) {
    if (n & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    n >>= 1;
  }
  return res;
}
void run() {
  int n, k;
  readln(n, k);
  vector<vector<pair<int, int>>> g(n);
  int u, v, x;
  for (int i = 0; i < (int)(n - 1); ++i)
    readln(u, v, x), --u, --v, g[u].push_back({v, x}), g[v].push_back({u, x});
  vector<long long> degs(n + 1, 0);
  for (int i = 1; i < (int)(n + 1); ++i) degs[i] = binpowmod(i * 1ll, k, MOD);
  vector<bool> used(n, false);
  function<int(int)> dfs = [&](int u) {
    used[u] = true;
    int cnt = 1;
    for (auto& [v, x] : g[u])
      if (!x && !used[v]) cnt += dfs(v);
    return cnt;
  };
  long long ans = degs[n];
  for (int i = 0; i < (int)(n); ++i)
    if (!used[i]) {
      int cnt = dfs(i);
      ans -= degs[cnt];
      if (ans < 0) ans += MOD;
    }
  writeln(ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  run();
  return 0;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T> const& _a);
template <class T1, class T2>
inline istream& operator>>(istream& is, pair<T1, T2>& _a) {
  return is >> _a.first >> _a.second;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& os, pair<T1, T2> const& _a) {
  return os << _a.first << " " << _a.second;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T> const& _a) {
  if (_a.size())
    os << _a[0];
  else
    os << "\n";
  for (int i = 1; i < (int)(_a.size()); ++i)
    os << "\n "[is_fundamental<T>::value] << _a[i];
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, valarray<T> const& _a) {
  if (_a.size())
    os << _a[0];
  else
    os << "\n";
  for (int i = 1; i < (int)(_a.size()); ++i)
    os << "\n "[is_fundamental<T>::value] << _a[i];
  return os;
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& _a) {
  for (int i = 0; i < (int)(_a.size()); ++i) is >> _a[i];
  return is;
}
template <class T>
inline istream& operator>>(istream& is, valarray<T>& _a) {
  for (int i = 0; i < (int)(_a.size()); ++i) is >> _a[i];
  return is;
}
template <class T>
inline void print(T&& _a) {
  cout << " " << _a;
}
template <class T>
inline void priws(T&& _a) {
  cout << _a;
}
template <class T>
inline void read(T& _a) {
  cin >> _a;
}
