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
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  vector<vector<pair<int, int>>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    int u, v, t;
    cin >> u >> v >> t;
    u--;
    v--;
    g[u].emplace_back(v, t);
    g[v].emplace_back(u, t);
  }

  vector<int> sz(N), mx(N);
  vector<bool> vis(N);
  vector<int> nds;

  auto DfsSz = [&](auto dfs, int x) -> void {
    vis[x] = true;
    sz[x] = 1;
    mx[x] = 0;
    nds.push_back(x);
    for (auto [u, t] : g[x]) {
      if (!vis[u]) {
        dfs(dfs, u);
        sz[x] += sz[u];
        mx[x] = max(mx[x], sz[u]);
      }
    }
  };

  constexpr int kP = 1'000'000'000 + 7;
  vector<vector<vector<pair<int, int>>>> vec(N, vector<vector<pair<int, int>>>(2));

  auto DfsPath = [&](auto dfs, int x, int f, int c, int y, int s = 0) -> void {
    vis[x] = true;
    (s += A[x]) %= kP;
    if (y > K) return;
    vec[f][c].emplace_back(y, s);
    for (auto [u, t] : g[x]) {
      if (!vis[u]) {
        dfs(dfs, u, f, t, y + (c != t), s);
      }
    }
  };

  int ans = 0;

  vector<vector<pair<int, int64_t>>> fw(2, vector<pair<int, int64_t>>(N + 1));

  auto Update = [&](int x, int p, int c, int v) {
    for (int i = p + 1; i <= N; i += i & -i) {
      fw[x][i].first += c;
      (fw[x][i].second += v) %= kP;
    }
  };

  auto Query = [&](int x, int p) {
    pair<int, int64_t> res{};
    for (int i = p + 1; i > 0; i -= i & -i) {
      res.first += fw[x][i].first;
      (res.second += fw[x][i].second) %= kP;
    }
    return res;
  };

  auto Dfs = [&](auto dfs, int x) -> void {
    nds.clear();
    DfsSz(DfsSz, x);
    int cent = -1;
    int M = nds.size();
    for (int u : nds) {
      if (max(mx[u], M - sz[u]) * 2 <= M) {
        cent = u;
      }
      vis[u] = false;
    }
    assert(cent != -1);
    vis[cent] = true;
    for (auto [u, t] : g[cent]) {
      if (!vis[u]) {
        DfsPath(DfsPath, u, u, t, 0);
      }
    }
    for (int u : nds) {
      vis[u] = false;
    }
    vis[cent] = true;
    (ans += A[cent]) %= kP;
    for (auto [u, t] : g[cent]) {
      for (int i = 0; i < 2; ++i) {
        for (auto [p, s] : vec[u][i]) {
          assert(p <= K);
          for (int j = 0; j < 2; ++j) {
            auto r = Query(j, K - p - (i != j));
            ans += (r.second + 1LL * (s + A[cent]) * r.first) % kP;
            ans %= kP;
          }
          ans = (0LL + ans + s + A[cent]) % kP;
        }
      }
      for (int i = 0; i < 2; ++i) {
        for (auto [p, s] : vec[u][i]) {
          Update(i, p, 1, s);
        }
      }
    }
    for (auto [u, t] : g[cent]) {
      for (int i = 0; i < 2; ++i) {
        for (auto [p, s] : vec[u][i]) {
          Update(i, p, -1, kP - s);
        }
        vec[u][i].clear();
      }
    }
    for (auto [u, t] : g[cent]) {
      if (!vis[u]) {
        dfs(dfs, u);
      }
    }
  };

  Dfs(Dfs, 0);
  cout << ans << "\n";
  return 0;
}
