#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010, P = 1000000007;
int n, K, rt, ans, lim;
int a[maxn], sz[maxn], c[2][maxn], cs[2][maxn];
bool solved[maxn];
vector<pair<int, int>> G[maxn];
void add(int *c, int p, int v) {
  for (p++; p <= lim; p += p & -p) {
    if ((c[p] += v) >= P) c[p] -= P;
  }
}
int query(int *c, int p) {
  int s = 0;
  for (p = min(lim, p + 1); p; p -= p & -p) {
    if ((s += c[p]) >= P) s -= P;
  }
  return s;
}
int main() {
  scanf("%d %d", &n, &K);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1, u, v, c; i < n; i++) {
    scanf("%d %d %d", &u, &v, &c);
    G[u].emplace_back(v, c), G[v].emplace_back(u, c);
  }
  function<void(int, int, int)> find_rt = [&](int v, int fa, int all) {
    sz[v] = 1;
    int mx = 0;
    for (auto &e : G[v]) {
      int u = e.first;
      if (u ^ fa && !solved[u]) {
        find_rt(u, v, all), sz[v] += sz[u];
        mx = max(mx, sz[u]);
      }
    }
    if (max(mx, all - sz[v]) * 2 <= all) rt = v;
  };
  function<void(int, int)> solve = [&](int v, int U) {
    solved[v] = 1;
    (ans += a[v]) %= P, lim = U;
    for (int col : {0, 1}) {
      fill(c[col], c[col] + lim + 1, 0);
      fill(cs[col], cs[col] + lim + 1, 0);
    }
    for (auto &e : G[v]) {
      int u = e.first;
      if (solved[u]) continue;
      vector<array<int, 2>> V;
      function<void(int, int, int, int, int)> dfs = [&](int x, int fa, int s,
                                                        int cnt, int lst) {
        sz[x] = 1;
        if (cnt <= K) {
          ans = (1LL * ans + a[v] + s) % P;
          V.push_back({cnt, s});
          for (int col : {0, 1}) {
            int rem = K - cnt - (col != e.second);
            if (rem < 0) continue;
            ans = (ans + 1LL * (a[v] + s) * query(c[col], rem)) % P;
            (ans += query(cs[col], rem)) %= P;
          }
        }
        for (auto &e : G[x])
          if (e.first ^ fa && !solved[e.first]) {
            dfs(e.first, x, (s + a[e.first]) % P, cnt + (e.second != lst),
                e.second);
            sz[x] += sz[e.first];
          }
      };
      dfs(u, v, a[u], 0, e.second);
      for (auto &p : V) {
        add(c[e.second], p[0], 1);
        add(cs[e.second], p[0], p[1]);
      }
    }
    for (auto &e : G[v]) {
      int u = e.first;
      if (!solved[u]) find_rt(u, v, sz[u]), solve(rt, sz[u]);
    }
  };
  find_rt(1, 0, n), solve(rt, n);
  printf("%d\n", ans);
  return 0;
}

### Prompt

Create a solution in CPP for 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;
const int maxn = 200010, P = 1000000007;
int n, K, rt, ans, lim;
int a[maxn], sz[maxn], c[2][maxn], cs[2][maxn];
bool solved[maxn];
vector<pair<int, int>> G[maxn];
void add(int *c, int p, int v) {
  for (p++; p <= lim; p += p & -p) {
    if ((c[p] += v) >= P) c[p] -= P;
  }
}
int query(int *c, int p) {
  int s = 0;
  for (p = min(lim, p + 1); p; p -= p & -p) {
    if ((s += c[p]) >= P) s -= P;
  }
  return s;
}
int main() {
  scanf("%d %d", &n, &K);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1, u, v, c; i < n; i++) {
    scanf("%d %d %d", &u, &v, &c);
    G[u].emplace_back(v, c), G[v].emplace_back(u, c);
  }
  function<void(int, int, int)> find_rt = [&](int v, int fa, int all) {
    sz[v] = 1;
    int mx = 0;
    for (auto &e : G[v]) {
      int u = e.first;
      if (u ^ fa && !solved[u]) {
        find_rt(u, v, all), sz[v] += sz[u];
        mx = max(mx, sz[u]);
      }
    }
    if (max(mx, all - sz[v]) * 2 <= all) rt = v;
  };
  function<void(int, int)> solve = [&](int v, int U) {
    solved[v] = 1;
    (ans += a[v]) %= P, lim = U;
    for (int col : {0, 1}) {
      fill(c[col], c[col] + lim + 1, 0);
      fill(cs[col], cs[col] + lim + 1, 0);
    }
    for (auto &e : G[v]) {
      int u = e.first;
      if (solved[u]) continue;
      vector<array<int, 2>> V;
      function<void(int, int, int, int, int)> dfs = [&](int x, int fa, int s,
                                                        int cnt, int lst) {
        sz[x] = 1;
        if (cnt <= K) {
          ans = (1LL * ans + a[v] + s) % P;
          V.push_back({cnt, s});
          for (int col : {0, 1}) {
            int rem = K - cnt - (col != e.second);
            if (rem < 0) continue;
            ans = (ans + 1LL * (a[v] + s) * query(c[col], rem)) % P;
            (ans += query(cs[col], rem)) %= P;
          }
        }
        for (auto &e : G[x])
          if (e.first ^ fa && !solved[e.first]) {
            dfs(e.first, x, (s + a[e.first]) % P, cnt + (e.second != lst),
                e.second);
            sz[x] += sz[e.first];
          }
      };
      dfs(u, v, a[u], 0, e.second);
      for (auto &p : V) {
        add(c[e.second], p[0], 1);
        add(cs[e.second], p[0], p[1]);
      }
    }
    for (auto &e : G[v]) {
      int u = e.first;
      if (!solved[u]) find_rt(u, v, sz[u]), solve(rt, sz[u]);
    }
  };
  find_rt(1, 0, n), solve(rt, n);
  printf("%d\n", ans);
  return 0;
}

```