#include <bits/stdc++.h>
using namespace std;
void abc() { cout << endl; }
template <typename T, typename... U>
void abc(T a, U... b) {
  cout << a << ' ', abc(b...);
}
template <typename T>
void printv(T l, T r) {
  while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B>
istream& operator>>(istream& o, pair<A, B>& a) {
  return o >> a.first >> a.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a) {
  return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T>
ostream& operator<<(ostream& o, vector<T> a) {
  bool is = false;
  for (T i : a) {
    o << (is ? ' ' : '{'), is = true, o << i;
  }
  return o << '}';
}
template <typename T>
struct vv : vector<vector<T>> {
  vv(int n, int m, T v) : vector<vector<T>>(n, vector<T>(m, v)) {}
  vv() {}
};
template <typename T>
struct vvv : vector<vv<T>> {
  vvv(int n, int m, int k, T v) : vector<vv<T>>(n, vv<T>(m, k, v)) {}
  vvv() {}
};
const int mod = 1e9 + 7, N = 200087, logN = 20, K = 111;
vector<pair<int, int>> adj[N];
vector<int> a;
int sz[N], k;
bool vis[N];
void dfs_sz(int v, int pa) {
  sz[v] = 1;
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u]) {
      dfs_sz(u, v);
      sz[v] += sz[u];
    }
}
int dfs_cen(int v, int pa, int n) {
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u] && sz[u] > n / 2) {
      return dfs_cen(u, v, n);
    }
  return v;
}
long long int sum[N], chg[N];
long long int val[N][4];
vector<int> mov[4];
void add(int p, long long int v, int t) {
  p++;
  for (int i = p; i < N; i += i & (-i))
    (val[i][t] += v) %= mod, mov[t].push_back(i);
}
long long int query(int p, int t) {
  p++;
  long long int ans = 0;
  for (int i = p; i > 0; i -= i & (-i)) {
    (ans += val[i][t]) %= mod;
  }
  return ans;
}
void rollback(int t) {
  while (!mov[t].empty()) {
    val[mov[t].back()][t] = 0, mov[t].pop_back();
  }
}
vector<int> now;
long long int ans = 0;
void dfs_ans(int v, int pa, int cc, int c) {
  if (~pa) now.push_back(v);
  sum[v] = ((~pa ? sum[pa] : 0) + a[v]) % mod;
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u]) {
      chg[u] = chg[v] + (!~pa ? 0 : (cc != t));
      dfs_ans(u, v, t, c);
      if (!~pa) {
        for (int v : now) {
          if (chg[v] <= k) (ans += sum[v]) %= mod;
          (ans += query(k - chg[v], t) +
                  query(k - chg[v], t | 2) * (sum[v] + mod - a[c]) % mod) %=
              mod;
          (ans += query(k - chg[v] - 1, t ^ 1) +
                  query(k - chg[v] - 1, (t ^ 1) | 2) * (sum[v] + mod - a[c]) %
                      mod) %= mod;
        }
        for (int v : now) {
          add(chg[v], sum[v], t);
          add(chg[v], 1, t | 2);
        }
        now.clear();
      }
    }
}
void dfs_cd(int v, int pa) {
  dfs_sz(v, pa);
  int c = dfs_cen(v, pa, sz[v]);
  vis[c] = true;
  chg[c] = 0;
  dfs_ans(c, -1, -1, c);
  rollback(0), rollback(1), rollback(2), rollback(3);
  for (auto [u, t] : adj[c])
    if (!vis[u]) {
      dfs_cd(u, c);
    }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> k;
  a.resize(n);
  for (int i = 0; i < n; ++i) cin >> a[i], (ans += a[i]) %= mod;
  for (int i = 0, u, v, t; i < n - 1; ++i) {
    cin >> u >> v >> t, --u, --v;
    adj[u].emplace_back(v, t);
    adj[v].emplace_back(u, t);
  }
  dfs_cd(0, -1);
  cout << ans << endl;
}

### Prompt

Please formulate a CPP solution to the following problem:

There is a city park represented as a tree with n attractions as its vertices and n - 1 rails as its edges. The i-th attraction has happiness value a_i.

Each rail has a color. It is either black if t_i = 0, or white if t_i = 1. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use 1 ticket.

The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have k tickets, meaning you can only switch train types at most k times. In particular, you do not need a ticket to go through a path consisting of one rail color.

Define f(u, v) as the sum of happiness values of the attractions in the tour (u, v), which is a simple path that starts at the u-th attraction and ends at the v-th attraction. Find the sum of f(u,v) for all valid tours (u, v) (1 ≤ u ≤ v ≤ n) that does not need more than k tickets, modulo 10^9 + 7.

Input

The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ n-1) — the number of attractions in the city park and the number of tickets you have.

The second line contains n integers a_1, a_2,…, a_n (0 ≤ a_i ≤ 10^9) — the happiness value of each attraction.

The i-th of the next n - 1 lines contains three integers u_i, v_i, and t_i (1 ≤ u_i, v_i ≤ n, 0 ≤ t_i ≤ 1) — an edge between vertices u_i and v_i with color t_i. The given edges form a tree.

Output

Output an integer denoting the total happiness value for all valid tours (u, v) (1 ≤ u ≤ v ≤ n), modulo 10^9 + 7.

Examples

Input


5 0
1 3 2 6 4
1 2 1
1 4 0
3 2 1
2 5 0


Output


45


Input


3 1
1 1 1
1 2 1
3 2 0


Output


10

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void abc() { cout << endl; }
template <typename T, typename... U>
void abc(T a, U... b) {
  cout << a << ' ', abc(b...);
}
template <typename T>
void printv(T l, T r) {
  while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B>
istream& operator>>(istream& o, pair<A, B>& a) {
  return o >> a.first >> a.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a) {
  return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T>
ostream& operator<<(ostream& o, vector<T> a) {
  bool is = false;
  for (T i : a) {
    o << (is ? ' ' : '{'), is = true, o << i;
  }
  return o << '}';
}
template <typename T>
struct vv : vector<vector<T>> {
  vv(int n, int m, T v) : vector<vector<T>>(n, vector<T>(m, v)) {}
  vv() {}
};
template <typename T>
struct vvv : vector<vv<T>> {
  vvv(int n, int m, int k, T v) : vector<vv<T>>(n, vv<T>(m, k, v)) {}
  vvv() {}
};
const int mod = 1e9 + 7, N = 200087, logN = 20, K = 111;
vector<pair<int, int>> adj[N];
vector<int> a;
int sz[N], k;
bool vis[N];
void dfs_sz(int v, int pa) {
  sz[v] = 1;
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u]) {
      dfs_sz(u, v);
      sz[v] += sz[u];
    }
}
int dfs_cen(int v, int pa, int n) {
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u] && sz[u] > n / 2) {
      return dfs_cen(u, v, n);
    }
  return v;
}
long long int sum[N], chg[N];
long long int val[N][4];
vector<int> mov[4];
void add(int p, long long int v, int t) {
  p++;
  for (int i = p; i < N; i += i & (-i))
    (val[i][t] += v) %= mod, mov[t].push_back(i);
}
long long int query(int p, int t) {
  p++;
  long long int ans = 0;
  for (int i = p; i > 0; i -= i & (-i)) {
    (ans += val[i][t]) %= mod;
  }
  return ans;
}
void rollback(int t) {
  while (!mov[t].empty()) {
    val[mov[t].back()][t] = 0, mov[t].pop_back();
  }
}
vector<int> now;
long long int ans = 0;
void dfs_ans(int v, int pa, int cc, int c) {
  if (~pa) now.push_back(v);
  sum[v] = ((~pa ? sum[pa] : 0) + a[v]) % mod;
  for (auto [u, t] : adj[v])
    if (u != pa && !vis[u]) {
      chg[u] = chg[v] + (!~pa ? 0 : (cc != t));
      dfs_ans(u, v, t, c);
      if (!~pa) {
        for (int v : now) {
          if (chg[v] <= k) (ans += sum[v]) %= mod;
          (ans += query(k - chg[v], t) +
                  query(k - chg[v], t | 2) * (sum[v] + mod - a[c]) % mod) %=
              mod;
          (ans += query(k - chg[v] - 1, t ^ 1) +
                  query(k - chg[v] - 1, (t ^ 1) | 2) * (sum[v] + mod - a[c]) %
                      mod) %= mod;
        }
        for (int v : now) {
          add(chg[v], sum[v], t);
          add(chg[v], 1, t | 2);
        }
        now.clear();
      }
    }
}
void dfs_cd(int v, int pa) {
  dfs_sz(v, pa);
  int c = dfs_cen(v, pa, sz[v]);
  vis[c] = true;
  chg[c] = 0;
  dfs_ans(c, -1, -1, c);
  rollback(0), rollback(1), rollback(2), rollback(3);
  for (auto [u, t] : adj[c])
    if (!vis[u]) {
      dfs_cd(u, c);
    }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> k;
  a.resize(n);
  for (int i = 0; i < n; ++i) cin >> a[i], (ans += a[i]) %= mod;
  for (int i = 0, u, v, t; i < n - 1; ++i) {
    cin >> u >> v >> t, --u, --v;
    adj[u].emplace_back(v, t);
    adj[v].emplace_back(u, t);
  }
  dfs_cd(0, -1);
  cout << ans << endl;
}

```