#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005, M = 1000000007;
int n, k;
int a[N];
vector<int> g[N], gc[N];
bool c[N];
int q[N];
void dfs0(int x, int p) {
  q[x] = 1;
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    dfs0(h, x);
    q[x] += q[h];
  }
}
int dfsc(int x, int p, int xx) {
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    if (q[h] > q[xx] / 2) return dfsc(h, x, xx);
  }
  return x;
}
int s[N];
void dfs1(int x, int p, int gg) {
  if (x == p)
    s[x] = a[x];
  else
    s[x] = (s[p] + a[x]) % M;
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    if (gg != -1 && gc[x][i] != gg)
      q[h] = q[x] + 1;
    else
      q[h] = q[x];
    dfs1(h, x, gc[x][i]);
  }
}
vector<int> v;
void dfs2(int x, int p) {
  v.push_back(x);
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    dfs2(h, x);
  }
}
pair<int, int> t[2][N * 4];
pair<int, int> mer(const pair<int, int>& a, const pair<int, int>& b) {
  return make_pair((a.first + b.first) % M, a.second + b.second);
}
void ubd(pair<int, int> t[], int tl, int tr, int x, int yf, int ys, int pos) {
  if (tl == tr) {
    t[pos].first = (t[pos].first + yf) % M;
    t[pos].second += ys;
    return;
  }
  int m = (tl + tr) / 2;
  if (x <= m)
    ubd(t, tl, m, x, yf, ys, pos * 2);
  else
    ubd(t, m + 1, tr, x, yf, ys, pos * 2 + 1);
  t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
pair<int, int> qry(pair<int, int> t[], int tl, int tr, int l, int r, int pos) {
  if (l > r) return make_pair(0, 0);
  if (tl == l && tr == r) return t[pos];
  int m = (tl + tr) / 2;
  return mer(qry(t, tl, m, l, min(m, r), pos * 2),
             qry(t, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
int ans;
void solvv(int r) {
  q[r] = 0;
  dfs1(r, r, -1);
  ans = (ans + a[r]) % M;
  for (int i = 0; i < g[r].size(); ++i) {
    int x = g[r][i];
    if (c[x]) continue;
    int xc = gc[r][i];
    v.clear();
    dfs2(x, r);
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ans = (ans + s[x]) % M;
      pair<int, int> u = qry(t[xc], 0, k, 0, k - q[x], 1);
      ans = (ans + u.first) % M;
      ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
      u = qry(t[(xc ^ 1)], 0, k, 0, k - q[x] - 1, 1);
      ans = (ans + u.first) % M;
      ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
    }
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ubd(t[xc], 0, k, q[x], s[x], 1, 1);
    }
  }
  for (int i = 0; i < g[r].size(); ++i) {
    int x = g[r][i];
    if (c[x]) continue;
    int xc = gc[r][i];
    v.clear();
    dfs2(x, r);
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ubd(t[xc], 0, k, q[x], -s[x], -1, 1);
    }
  }
}
void solv() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 0; i < n - 1; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    g[x].push_back(y);
    g[y].push_back(x);
    gc[x].push_back(z);
    gc[y].push_back(z);
  }
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    dfs0(x, x);
    x = dfsc(x, x, x);
    solvv(x);
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      q.push(h);
    }
    c[x] = true;
  }
  ans = (ans + M) % M;
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int tt = 1;
  while (tt--) solv();
  return 0;
}

### Prompt

Please formulate 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>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005, M = 1000000007;
int n, k;
int a[N];
vector<int> g[N], gc[N];
bool c[N];
int q[N];
void dfs0(int x, int p) {
  q[x] = 1;
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    dfs0(h, x);
    q[x] += q[h];
  }
}
int dfsc(int x, int p, int xx) {
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    if (q[h] > q[xx] / 2) return dfsc(h, x, xx);
  }
  return x;
}
int s[N];
void dfs1(int x, int p, int gg) {
  if (x == p)
    s[x] = a[x];
  else
    s[x] = (s[p] + a[x]) % M;
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    if (gg != -1 && gc[x][i] != gg)
      q[h] = q[x] + 1;
    else
      q[h] = q[x];
    dfs1(h, x, gc[x][i]);
  }
}
vector<int> v;
void dfs2(int x, int p) {
  v.push_back(x);
  for (int i = 0; i < g[x].size(); ++i) {
    int h = g[x][i];
    if (c[h]) continue;
    if (h == p) continue;
    dfs2(h, x);
  }
}
pair<int, int> t[2][N * 4];
pair<int, int> mer(const pair<int, int>& a, const pair<int, int>& b) {
  return make_pair((a.first + b.first) % M, a.second + b.second);
}
void ubd(pair<int, int> t[], int tl, int tr, int x, int yf, int ys, int pos) {
  if (tl == tr) {
    t[pos].first = (t[pos].first + yf) % M;
    t[pos].second += ys;
    return;
  }
  int m = (tl + tr) / 2;
  if (x <= m)
    ubd(t, tl, m, x, yf, ys, pos * 2);
  else
    ubd(t, m + 1, tr, x, yf, ys, pos * 2 + 1);
  t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
pair<int, int> qry(pair<int, int> t[], int tl, int tr, int l, int r, int pos) {
  if (l > r) return make_pair(0, 0);
  if (tl == l && tr == r) return t[pos];
  int m = (tl + tr) / 2;
  return mer(qry(t, tl, m, l, min(m, r), pos * 2),
             qry(t, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
int ans;
void solvv(int r) {
  q[r] = 0;
  dfs1(r, r, -1);
  ans = (ans + a[r]) % M;
  for (int i = 0; i < g[r].size(); ++i) {
    int x = g[r][i];
    if (c[x]) continue;
    int xc = gc[r][i];
    v.clear();
    dfs2(x, r);
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ans = (ans + s[x]) % M;
      pair<int, int> u = qry(t[xc], 0, k, 0, k - q[x], 1);
      ans = (ans + u.first) % M;
      ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
      u = qry(t[(xc ^ 1)], 0, k, 0, k - q[x] - 1, 1);
      ans = (ans + u.first) % M;
      ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
    }
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ubd(t[xc], 0, k, q[x], s[x], 1, 1);
    }
  }
  for (int i = 0; i < g[r].size(); ++i) {
    int x = g[r][i];
    if (c[x]) continue;
    int xc = gc[r][i];
    v.clear();
    dfs2(x, r);
    for (int i = 0; i < ((int)(v).size()); ++i) {
      int x = v[i];
      if (q[x] > k) continue;
      ubd(t[xc], 0, k, q[x], -s[x], -1, 1);
    }
  }
}
void solv() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 0; i < n - 1; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    g[x].push_back(y);
    g[y].push_back(x);
    gc[x].push_back(z);
    gc[y].push_back(z);
  }
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    dfs0(x, x);
    x = dfsc(x, x, x);
    solvv(x);
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      q.push(h);
    }
    c[x] = true;
  }
  ans = (ans + M) % M;
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int tt = 1;
  while (tt--) solv();
  return 0;
}

```