#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 200005;
const int mod = 1e9 + 7;
const int inf = 1e9;
inline void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
vector<pair<int, int> > adj[N];
int a[N], n, LIM;
bool ban[N];
int sz[N], maxp[N], sumsz, rt;
void getrt(int u, int fa) {
  maxp[u] = 0, sz[u] = 1;
  for (auto v : adj[u]) {
    if (ban[v.first] || v.first == fa) continue;
    getrt(v.first, u);
    sz[u] += sz[v.first];
    ckmax(maxp[u], sz[v.first]);
  }
  ckmax(maxp[u], sumsz - sz[u]);
  if (maxp[u] < maxp[rt]) rt = u;
}
vector<pair<int, int> > tmp, tmq[2];
int ans;
void dfs1(int u, int fa, int lst, int turns, int sum) {
  sum = (sum + a[u]) % mod;
  tmp.push_back({turns, sum});
  for (auto v : adj[u]) {
    if (ban[v.first] || v.first == fa) continue;
    dfs1(v.first, u, v.second, turns + (lst != v.second), sum);
  }
}
int calc1(vector<pair<int, int> > x) {
  static int zz[N];
  int n = (int(x.size())), res = 0;
  for (int i = 0; i < n; i++) zz[i] = x[i].second;
  for (int i = 1; i < n; i++) add(x[i].second, x[i - 1].second);
  for (int i = 0; i < n; i++) {
    int t = upper_bound(x.begin(), x.end(), make_pair(LIM - x[i].first, mod)) -
            x.begin() - 1;
    ckmin(t, i - 1);
    if (t >= 0) add(res, (x[t].second + 1ll * (t + 1) * (zz[i] + a[rt])) % mod);
  }
  return res;
}
int calc2(vector<pair<int, int> > x, vector<pair<int, int> > y) {
  int n = (int(x.size())), m = (int(y.size())), res = 0;
  for (int i = 1; i < n; i++) add(x[i].second, x[i - 1].second);
  for (int i = 0; i < m; i++) {
    int t =
        upper_bound(x.begin(), x.end(), make_pair(LIM - y[i].first - 1, mod)) -
        x.begin() - 1;
    if (t >= 0)
      add(res, (x[t].second + 1ll * (t + 1) * (y[i].second + a[rt])) % mod);
  }
  return res;
}
void calc_in(int u) {
  sort(tmp.begin(), tmp.end());
  for (auto v : tmp)
    if (v.first <= LIM) add(ans, (v.second + a[u]) % mod);
  sub(ans, calc1(tmp));
}
void dfz(int u) {
  ban[u] = 1;
  tmq[0].clear(), tmq[1].clear();
  add(ans, a[u]);
  for (auto v : adj[u]) {
    if (!ban[v.first]) {
      tmp.clear();
      dfs1(v.first, u, v.second, 0, 0);
      for (auto it : tmp) tmq[v.second].push_back(it);
      calc_in(u);
    }
  }
  sort(tmq[0].begin(), tmq[0].end());
  sort(tmq[1].begin(), tmq[1].end());
  add(ans, calc1(tmq[0]));
  add(ans, calc1(tmq[1]));
  add(ans, calc2(tmq[0], tmq[1]));
  for (auto v : adj[u]) {
    if (!ban[v.first]) {
      rt = 0, sumsz = sz[v.first], getrt(v.first, 0);
      dfz(rt);
    }
  }
}
int main() {
  n = read(), LIM = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= n - 1; i++) {
    int u = read(), v = read(), w = read();
    adj[u].push_back({v, w}), adj[v].push_back({u, w});
  }
  maxp[rt = 0] = n, sumsz = n, getrt(1, 0);
  dfz(rt);
  print(ans, '\n');
  return 0;
}

### Prompt

Generate 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>
#pragma GCC optimize(2, 3, "Ofast")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 200005;
const int mod = 1e9 + 7;
const int inf = 1e9;
inline void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) x += mod;
}
vector<pair<int, int> > adj[N];
int a[N], n, LIM;
bool ban[N];
int sz[N], maxp[N], sumsz, rt;
void getrt(int u, int fa) {
  maxp[u] = 0, sz[u] = 1;
  for (auto v : adj[u]) {
    if (ban[v.first] || v.first == fa) continue;
    getrt(v.first, u);
    sz[u] += sz[v.first];
    ckmax(maxp[u], sz[v.first]);
  }
  ckmax(maxp[u], sumsz - sz[u]);
  if (maxp[u] < maxp[rt]) rt = u;
}
vector<pair<int, int> > tmp, tmq[2];
int ans;
void dfs1(int u, int fa, int lst, int turns, int sum) {
  sum = (sum + a[u]) % mod;
  tmp.push_back({turns, sum});
  for (auto v : adj[u]) {
    if (ban[v.first] || v.first == fa) continue;
    dfs1(v.first, u, v.second, turns + (lst != v.second), sum);
  }
}
int calc1(vector<pair<int, int> > x) {
  static int zz[N];
  int n = (int(x.size())), res = 0;
  for (int i = 0; i < n; i++) zz[i] = x[i].second;
  for (int i = 1; i < n; i++) add(x[i].second, x[i - 1].second);
  for (int i = 0; i < n; i++) {
    int t = upper_bound(x.begin(), x.end(), make_pair(LIM - x[i].first, mod)) -
            x.begin() - 1;
    ckmin(t, i - 1);
    if (t >= 0) add(res, (x[t].second + 1ll * (t + 1) * (zz[i] + a[rt])) % mod);
  }
  return res;
}
int calc2(vector<pair<int, int> > x, vector<pair<int, int> > y) {
  int n = (int(x.size())), m = (int(y.size())), res = 0;
  for (int i = 1; i < n; i++) add(x[i].second, x[i - 1].second);
  for (int i = 0; i < m; i++) {
    int t =
        upper_bound(x.begin(), x.end(), make_pair(LIM - y[i].first - 1, mod)) -
        x.begin() - 1;
    if (t >= 0)
      add(res, (x[t].second + 1ll * (t + 1) * (y[i].second + a[rt])) % mod);
  }
  return res;
}
void calc_in(int u) {
  sort(tmp.begin(), tmp.end());
  for (auto v : tmp)
    if (v.first <= LIM) add(ans, (v.second + a[u]) % mod);
  sub(ans, calc1(tmp));
}
void dfz(int u) {
  ban[u] = 1;
  tmq[0].clear(), tmq[1].clear();
  add(ans, a[u]);
  for (auto v : adj[u]) {
    if (!ban[v.first]) {
      tmp.clear();
      dfs1(v.first, u, v.second, 0, 0);
      for (auto it : tmp) tmq[v.second].push_back(it);
      calc_in(u);
    }
  }
  sort(tmq[0].begin(), tmq[0].end());
  sort(tmq[1].begin(), tmq[1].end());
  add(ans, calc1(tmq[0]));
  add(ans, calc1(tmq[1]));
  add(ans, calc2(tmq[0], tmq[1]));
  for (auto v : adj[u]) {
    if (!ban[v.first]) {
      rt = 0, sumsz = sz[v.first], getrt(v.first, 0);
      dfz(rt);
    }
  }
}
int main() {
  n = read(), LIM = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  for (int i = 1; i <= n - 1; i++) {
    int u = read(), v = read(), w = read();
    adj[u].push_back({v, w}), adj[v].push_back({u, w});
  }
  maxp[rt = 0] = n, sumsz = n, getrt(1, 0);
  dfz(rt);
  print(ans, '\n');
  return 0;
}

```