#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long k = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    k = k * 10 + ch - '0';
    ch = getchar();
  }
  return k * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long N = 2e5 + 10;
const long long MOD = 1e9 + 7;
long long nedge = 0, p[2 * N], nex[2 * N], head[2 * N], c[2 * N];
long long n, deep[N], Deep[N][2], dep[N], Dep[N][2];
long long s[N], f[N], vis[N], sum, rt, ans = 0, d[N], K;
long long maxx = 0, Maxx = 0, a[N];
inline void upd(long long &x, long long v) { x = (x + v) % MOD; }
inline void addedge(long long x, long long y, long long z) {
  p[++nedge] = y;
  c[nedge] = z;
  nex[nedge] = head[x];
  head[x] = nedge;
}
inline void dfs(long long x, long long fa) {
  s[x] = 1;
  f[x] = 0;
  for (long long k = head[x]; k; k = nex[k])
    if (p[k] != fa && !vis[p[k]]) {
      dfs(p[k], x);
      s[x] += s[p[k]];
      f[x] = max(f[x], s[p[k]]);
    }
  f[x] = max(f[x], sum - s[x]);
  if (f[x] < f[rt]) rt = x;
}
inline void dfss(long long x, long long fa, long long ps, long long v) {
  if (d[x] > K) return;
  maxx = max(maxx, d[x]);
  upd(v, a[x]);
  upd(deep[d[x]], v);
  upd(dep[d[x]], 1);
  for (long long k = head[x]; k; k = nex[k])
    if (p[k] != fa && !vis[p[k]]) {
      if (ps == c[k])
        d[p[k]] = d[x];
      else
        d[p[k]] = d[x] + 1;
      dfss(p[k], x, c[k], v);
    }
}
inline void cal(long long x) {
  upd(ans, a[x]);
  for (long long i = 0; i <= Maxx; i++) {
    Deep[i][0] = Deep[i][1] = 0;
    Dep[i][0] = Dep[i][1] = 0;
    deep[i] = dep[i] = 0;
  }
  d[x] = Maxx = 0;
  for (long long k = head[x]; k; k = nex[k])
    if (!vis[p[k]]) {
      for (long long i = 0; i <= Maxx; i++) deep[i] = dep[i] = 0;
      maxx = 0;
      d[p[k]] = 0;
      dfss(p[k], x, c[k], 0);
      for (long long i = 0; i <= maxx; i++) {
        upd(ans, ((deep[i] * Dep[min(Maxx, K - i)][c[k]]) % MOD +
                  (Deep[min(Maxx, K - i)][c[k]] * dep[i]) % MOD) %
                     MOD);
        upd(ans, dep[i] * Dep[min(Maxx, K - i)][c[k]] % MOD * a[x] % MOD);
        if (K - i - 1 >= 0) {
          upd(ans, ((deep[i] * Dep[min(Maxx, K - i - 1)][c[k] ^ 1]) % MOD +
                    (Deep[min(Maxx, K - i - 1)][c[k] ^ 1] * dep[i]) % MOD) %
                       MOD);
          upd(ans,
              dep[i] * Dep[min(Maxx, K - i - 1)][c[k] ^ 1] % MOD * a[x] % MOD);
        }
      }
      while (Maxx < maxx) {
        Maxx++;
        Deep[Maxx][0] = Deep[Maxx - 1][0];
        Deep[Maxx][1] = Deep[Maxx - 1][1];
        Dep[Maxx][0] = Dep[Maxx - 1][0];
        Dep[Maxx][1] = Dep[Maxx - 1][1];
      }
      for (long long i = 0; i <= Maxx; i++) {
        if (i) {
          upd(deep[i], deep[i - 1]);
          upd(dep[i], dep[i - 1]);
        }
        if (i == Maxx) upd(ans, (deep[i] + a[x] * dep[i] % MOD) % MOD);
        upd(Deep[i][c[k]], deep[i]);
        upd(Dep[i][c[k]], dep[i]);
      }
    }
}
inline void work(long long x) {
  vis[x] = 1;
  cal(x);
  for (long long k = head[x]; k; k = nex[k])
    if (!vis[p[k]]) {
      sum = s[p[k]];
      rt = 0;
      dfs(p[k], 0);
      work(rt);
    }
}
signed main() {
  n = read();
  K = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 1; i < n; i++) {
    long long x = read(), y = read(), v = read();
    addedge(x, y, v);
    addedge(y, x, v);
  }
  f[0] = 1e9;
  sum = n;
  dfs(1, 0);
  work(rt);
  writeln(ans);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
inline long long read() {
  long long k = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    k = k * 10 + ch - '0';
    ch = getchar();
  }
  return k * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long N = 2e5 + 10;
const long long MOD = 1e9 + 7;
long long nedge = 0, p[2 * N], nex[2 * N], head[2 * N], c[2 * N];
long long n, deep[N], Deep[N][2], dep[N], Dep[N][2];
long long s[N], f[N], vis[N], sum, rt, ans = 0, d[N], K;
long long maxx = 0, Maxx = 0, a[N];
inline void upd(long long &x, long long v) { x = (x + v) % MOD; }
inline void addedge(long long x, long long y, long long z) {
  p[++nedge] = y;
  c[nedge] = z;
  nex[nedge] = head[x];
  head[x] = nedge;
}
inline void dfs(long long x, long long fa) {
  s[x] = 1;
  f[x] = 0;
  for (long long k = head[x]; k; k = nex[k])
    if (p[k] != fa && !vis[p[k]]) {
      dfs(p[k], x);
      s[x] += s[p[k]];
      f[x] = max(f[x], s[p[k]]);
    }
  f[x] = max(f[x], sum - s[x]);
  if (f[x] < f[rt]) rt = x;
}
inline void dfss(long long x, long long fa, long long ps, long long v) {
  if (d[x] > K) return;
  maxx = max(maxx, d[x]);
  upd(v, a[x]);
  upd(deep[d[x]], v);
  upd(dep[d[x]], 1);
  for (long long k = head[x]; k; k = nex[k])
    if (p[k] != fa && !vis[p[k]]) {
      if (ps == c[k])
        d[p[k]] = d[x];
      else
        d[p[k]] = d[x] + 1;
      dfss(p[k], x, c[k], v);
    }
}
inline void cal(long long x) {
  upd(ans, a[x]);
  for (long long i = 0; i <= Maxx; i++) {
    Deep[i][0] = Deep[i][1] = 0;
    Dep[i][0] = Dep[i][1] = 0;
    deep[i] = dep[i] = 0;
  }
  d[x] = Maxx = 0;
  for (long long k = head[x]; k; k = nex[k])
    if (!vis[p[k]]) {
      for (long long i = 0; i <= Maxx; i++) deep[i] = dep[i] = 0;
      maxx = 0;
      d[p[k]] = 0;
      dfss(p[k], x, c[k], 0);
      for (long long i = 0; i <= maxx; i++) {
        upd(ans, ((deep[i] * Dep[min(Maxx, K - i)][c[k]]) % MOD +
                  (Deep[min(Maxx, K - i)][c[k]] * dep[i]) % MOD) %
                     MOD);
        upd(ans, dep[i] * Dep[min(Maxx, K - i)][c[k]] % MOD * a[x] % MOD);
        if (K - i - 1 >= 0) {
          upd(ans, ((deep[i] * Dep[min(Maxx, K - i - 1)][c[k] ^ 1]) % MOD +
                    (Deep[min(Maxx, K - i - 1)][c[k] ^ 1] * dep[i]) % MOD) %
                       MOD);
          upd(ans,
              dep[i] * Dep[min(Maxx, K - i - 1)][c[k] ^ 1] % MOD * a[x] % MOD);
        }
      }
      while (Maxx < maxx) {
        Maxx++;
        Deep[Maxx][0] = Deep[Maxx - 1][0];
        Deep[Maxx][1] = Deep[Maxx - 1][1];
        Dep[Maxx][0] = Dep[Maxx - 1][0];
        Dep[Maxx][1] = Dep[Maxx - 1][1];
      }
      for (long long i = 0; i <= Maxx; i++) {
        if (i) {
          upd(deep[i], deep[i - 1]);
          upd(dep[i], dep[i - 1]);
        }
        if (i == Maxx) upd(ans, (deep[i] + a[x] * dep[i] % MOD) % MOD);
        upd(Deep[i][c[k]], deep[i]);
        upd(Dep[i][c[k]], dep[i]);
      }
    }
}
inline void work(long long x) {
  vis[x] = 1;
  cal(x);
  for (long long k = head[x]; k; k = nex[k])
    if (!vis[p[k]]) {
      sum = s[p[k]];
      rt = 0;
      dfs(p[k], 0);
      work(rt);
    }
}
signed main() {
  n = read();
  K = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 1; i < n; i++) {
    long long x = read(), y = read(), v = read();
    addedge(x, y, v);
    addedge(y, x, v);
  }
  f[0] = 1e9;
  sum = n;
  dfs(1, 0);
  work(rt);
  writeln(ans);
  return 0;
}

```