#include <bits/stdc++.h>
constexpr int Maxn = 2e5 + 7;
constexpr int Maxm = 1e6 + 7;
constexpr int Mod = 1e9 + 7;
int n, k, sum, root;
void add(int bit[], int p, int v) {
  for (; p < Maxn; p += p & -p) bit[p] = (bit[p] + v) % Mod;
}
int query(int bit[], int p) {
  int res = 0;
  for (; p; p -= p & -p) res = (res + bit[p]) % Mod;
  return res;
}
struct Edge {
  int nxt, to, w;
} e[Maxn << 1];
int head[Maxn], edge_cnt, res;
inline void add_edge(int u, int v, int w) {
  e[++edge_cnt].to = v;
  e[edge_cnt].nxt = head[u];
  e[edge_cnt].w = w;
  head[u] = edge_cnt;
}
int a[Maxn], siz[Maxn], f[Maxn];
int del[Maxn];
void getroot(int u, int fa) {
  siz[u] = 1;
  f[u] = 0;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (!del[v] && v != fa) {
      getroot(v, u);
      siz[u] += siz[v];
      f[u] = std::max(f[u], siz[v]);
    }
  }
  f[u] = std::max(f[u], sum - siz[u]);
  if (f[u] < f[root]) root = u;
}
int val[2][Maxn], num[2][Maxn];
void DFS(int u, int fa, int rcol, int col, int nxt, int tot, int opt) {
  tot = (tot + a[u]) % Mod;
  if (opt == 0) {
    if (k >= nxt) {
      int cnt = query(num[rcol], k - nxt + 1);
      int cur = query(val[rcol], k - nxt + 1);
      res = (res + 1LL * cnt * tot % Mod) % Mod;
      res = (res + cur) % Mod;
    }
    if (k >= nxt + 1) {
      int cnt = query(num[rcol ^ 1], k - nxt);
      int cur = query(val[rcol ^ 1], k - nxt);
      res = (res + 1LL * cnt * tot % Mod) % Mod;
      res = (res + cur) % Mod;
    }
    if (k >= nxt) res = (res + tot) % Mod;
  } else if (opt == 1) {
    add(num[rcol], nxt + 1, 1);
    add(val[rcol], nxt + 1, tot);
  } else {
    add(num[rcol], nxt + 1, Mod - 1);
    add(val[rcol], nxt + 1, Mod - tot);
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (del[v] || v == fa) continue;
    int nxtstp = nxt;
    if (w != col) ++nxtstp;
    DFS(v, u, rcol, w, nxtstp, tot, opt);
  }
}
void solve(int u) {
  del[u] = 1;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (!del[v]) {
      DFS(v, u, w, w, 0, a[u], 0);
      DFS(v, u, w, w, 0, 0, 1);
    }
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (!del[v]) DFS(v, u, w, w, 0, 0, -1);
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (!del[v]) {
      root = 0, sum = siz[v];
      getroot(v, 0);
      solve(root);
    }
  }
}
int main() {
  scanf("%d%d", &n, &k);
  f[0] = sum = n;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1, u, v, w; i <= n - 1; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w), add_edge(v, u, w);
  }
  getroot(1, 0);
  solve(root);
  for (int i = 1; i <= n; ++i) res = (res + a[i]) % Mod;
  printf("%d\n", res);
}

### 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>
constexpr int Maxn = 2e5 + 7;
constexpr int Maxm = 1e6 + 7;
constexpr int Mod = 1e9 + 7;
int n, k, sum, root;
void add(int bit[], int p, int v) {
  for (; p < Maxn; p += p & -p) bit[p] = (bit[p] + v) % Mod;
}
int query(int bit[], int p) {
  int res = 0;
  for (; p; p -= p & -p) res = (res + bit[p]) % Mod;
  return res;
}
struct Edge {
  int nxt, to, w;
} e[Maxn << 1];
int head[Maxn], edge_cnt, res;
inline void add_edge(int u, int v, int w) {
  e[++edge_cnt].to = v;
  e[edge_cnt].nxt = head[u];
  e[edge_cnt].w = w;
  head[u] = edge_cnt;
}
int a[Maxn], siz[Maxn], f[Maxn];
int del[Maxn];
void getroot(int u, int fa) {
  siz[u] = 1;
  f[u] = 0;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (!del[v] && v != fa) {
      getroot(v, u);
      siz[u] += siz[v];
      f[u] = std::max(f[u], siz[v]);
    }
  }
  f[u] = std::max(f[u], sum - siz[u]);
  if (f[u] < f[root]) root = u;
}
int val[2][Maxn], num[2][Maxn];
void DFS(int u, int fa, int rcol, int col, int nxt, int tot, int opt) {
  tot = (tot + a[u]) % Mod;
  if (opt == 0) {
    if (k >= nxt) {
      int cnt = query(num[rcol], k - nxt + 1);
      int cur = query(val[rcol], k - nxt + 1);
      res = (res + 1LL * cnt * tot % Mod) % Mod;
      res = (res + cur) % Mod;
    }
    if (k >= nxt + 1) {
      int cnt = query(num[rcol ^ 1], k - nxt);
      int cur = query(val[rcol ^ 1], k - nxt);
      res = (res + 1LL * cnt * tot % Mod) % Mod;
      res = (res + cur) % Mod;
    }
    if (k >= nxt) res = (res + tot) % Mod;
  } else if (opt == 1) {
    add(num[rcol], nxt + 1, 1);
    add(val[rcol], nxt + 1, tot);
  } else {
    add(num[rcol], nxt + 1, Mod - 1);
    add(val[rcol], nxt + 1, Mod - tot);
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (del[v] || v == fa) continue;
    int nxtstp = nxt;
    if (w != col) ++nxtstp;
    DFS(v, u, rcol, w, nxtstp, tot, opt);
  }
}
void solve(int u) {
  del[u] = 1;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (!del[v]) {
      DFS(v, u, w, w, 0, a[u], 0);
      DFS(v, u, w, w, 0, 0, 1);
    }
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to, w = e[i].w;
    if (!del[v]) DFS(v, u, w, w, 0, 0, -1);
  }
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (!del[v]) {
      root = 0, sum = siz[v];
      getroot(v, 0);
      solve(root);
    }
  }
}
int main() {
  scanf("%d%d", &n, &k);
  f[0] = sum = n;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1, u, v, w; i <= n - 1; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w), add_edge(v, u, w);
  }
  getroot(1, 0);
  solve(root);
  for (int i = 1; i <= n; ++i) res = (res + a[i]) % Mod;
  printf("%d\n", res);
}

```