#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T &a, const T &b) {
  return (a > b ? a = b, 1 : 0);
}
template <class T>
bool umax(T &a, const T &b) {
  return (a < b ? a = b, 1 : 0);
}
void INPUT(bool F = 0) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (F) {
    freopen(
        "name"
        ".in",
        "r", stdin);
    freopen(
        "name"
        ".out",
        "w", stdout);
  }
}
const int N = 2e5 + 1;
const int M = 1e9 + 7;
void add(int &a, int b) {
  a += b;
  if (a >= M)
    a -= M;
  else if (a < 0)
    a += M;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}
int mult(int a, int b) { return 1ll * a * b % M; }
int binpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mult(ans, a);
    b >>= 1;
    a = mult(a, a);
  }
  return ans;
}
vector<pair<int, int>> g[N];
vector<int> cord;
vector<array<int, 4>> cen[N];
struct mypref {
  vector<pair<int, int>> xs;
  vector<int> prefs;
  void build() {
    sort((xs).begin(), (xs).end());
    vector<pair<int, int>> vc;
    for (auto &z : xs) {
      if (!(int)(vc).size() || vc.back().first != z.first)
        vc.push_back({z.first, z.second});
      else
        add(vc.back().second, z.second);
    }
    for (int i = 0; i < (int)(vc).size(); i++) prefs.push_back(vc[i].second);
    for (int i = 1; i < (int)(vc).size(); i++) add(prefs[i], prefs[i - 1]);
    xs = vc;
  }
  int get(int id) {
    int l = 0, r = (int)(xs).size();
    while (l != r) {
      int tm = (l + r) >> 1;
      if (xs[tm].first > id)
        r = tm;
      else
        l = tm + 1;
    }
    l--;
    id = l;
    if (id == -1) return 0;
    return prefs[id];
  }
};
vector<mypref> pref1[N][2];
vector<mypref> prefas[N][2];
mypref PREF1[N][2];
mypref PREFas[N][2];
int dp[N], a[N], was[N], last[N], k;
int ans = 0;
void calc_sizes(int v, int p) {
  dp[v] = 1;
  for (auto &z : g[v]) {
    if (was[z.first] || z.first == p) continue;
    calc_sizes(z.first, v);
    dp[v] += dp[z.first];
  }
}
int get_centroid(int v, int p, int szz) {
  for (auto &z : g[v]) {
    if (z.first == p || was[z.first]) continue;
    if (dp[z.first] >= szz / 2) return get_centroid(z.first, v, szz);
  }
  return v;
}
void dfs_down(int v, int fi, int lst, int sm, int cost, int p, int tt) {
  add(sm, a[v]);
  if (cost <= k) add(ans, sm);
  if (cost <= k) add(ans, sm);
  cen[v].push_back({cen[p].back()[0], cost, fi, sum(sm, -a[cen[p].back()[0]])});
  pref1[cen[v].back()[0]][fi][tt].xs.push_back({cost, 1});
  prefas[cen[v].back()[0]][fi][tt].xs.push_back({cost, sm});
  PREF1[cen[v].back()[0]][fi].xs.push_back({cost, 1});
  PREFas[cen[v].back()[0]][fi].xs.push_back({cost, sm});
  last[v] = tt;
  for (auto &z : g[v]) {
    if (was[z.first] || z.first == p) continue;
    dfs_down(z.first, fi, z.second, sm, cost + (lst != z.second), v, tt);
  }
}
void get(int v) {
  int j = (int)(cen[v]).size() - 1, id = -1;
  while (1) {
    if (id != -1) {
      int first = cen[v][j][2];
      int me = cen[v][j][3];
      int ce = cen[v][j][0];
      for (int second = 0; second < 2; second++) {
        int how = k - (first != second) - cen[v][j][1];
        int hex = 0;
        add(hex, -mult(me, pref1[ce][second][id].get(how)));
        add(hex, -prefas[ce][second][id].get(how));
        add(hex, mult(me, PREF1[ce][second].get(how)));
        add(hex, PREFas[ce][second].get(how));
        add(ans, hex);
      }
    }
    id = last[cen[v][j][0]];
    j--;
    if (j < 0) break;
  }
}
void build(int v) {
  calc_sizes(v, v);
  v = get_centroid(v, v, dp[v]);
  was[v] = 1;
  cen[v].push_back({v, 0, -1, a[v]});
  int how = 0;
  for (auto &z : g[v])
    if (!was[z.first]) ++how;
  for (int j = 0; j < 2; j++) pref1[v][j].resize(how), prefas[v][j].resize(how);
  how = 0;
  for (auto &z : g[v]) {
    if (was[z.first]) continue;
    dfs_down(z.first, z.second, z.second, a[v], 0, v, how);
    pref1[v][0][how].build();
    pref1[v][1][how].build();
    prefas[v][0][how].build();
    prefas[v][1][how].build();
    ++how;
  }
  PREF1[v][0].build();
  PREF1[v][1].build();
  PREFas[v][0].build();
  PREFas[v][1].build();
  for (auto &z : g[v]) {
    if (!was[z.first]) build(z.first);
  }
}
signed main() {
  INPUT();
  int n;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 1; i < n; i++) {
    int v, u, c;
    cin >> v >> u >> c;
    --v;
    --u;
    g[v].push_back({u, c});
    g[u].push_back({v, c});
  }
  build(0);
  for (int i = 0; i < n; i++) get(i);
  int obr = binpow(2, M - 2);
  ans = mult(ans, obr);
  for (int i = 0; i < n; i++) add(ans, a[i]);
  cout << ans;
  return 0;
}

### Prompt

Your task is to create 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;
template <class T>
bool umin(T &a, const T &b) {
  return (a > b ? a = b, 1 : 0);
}
template <class T>
bool umax(T &a, const T &b) {
  return (a < b ? a = b, 1 : 0);
}
void INPUT(bool F = 0) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (F) {
    freopen(
        "name"
        ".in",
        "r", stdin);
    freopen(
        "name"
        ".out",
        "w", stdout);
  }
}
const int N = 2e5 + 1;
const int M = 1e9 + 7;
void add(int &a, int b) {
  a += b;
  if (a >= M)
    a -= M;
  else if (a < 0)
    a += M;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}
int mult(int a, int b) { return 1ll * a * b % M; }
int binpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = mult(ans, a);
    b >>= 1;
    a = mult(a, a);
  }
  return ans;
}
vector<pair<int, int>> g[N];
vector<int> cord;
vector<array<int, 4>> cen[N];
struct mypref {
  vector<pair<int, int>> xs;
  vector<int> prefs;
  void build() {
    sort((xs).begin(), (xs).end());
    vector<pair<int, int>> vc;
    for (auto &z : xs) {
      if (!(int)(vc).size() || vc.back().first != z.first)
        vc.push_back({z.first, z.second});
      else
        add(vc.back().second, z.second);
    }
    for (int i = 0; i < (int)(vc).size(); i++) prefs.push_back(vc[i].second);
    for (int i = 1; i < (int)(vc).size(); i++) add(prefs[i], prefs[i - 1]);
    xs = vc;
  }
  int get(int id) {
    int l = 0, r = (int)(xs).size();
    while (l != r) {
      int tm = (l + r) >> 1;
      if (xs[tm].first > id)
        r = tm;
      else
        l = tm + 1;
    }
    l--;
    id = l;
    if (id == -1) return 0;
    return prefs[id];
  }
};
vector<mypref> pref1[N][2];
vector<mypref> prefas[N][2];
mypref PREF1[N][2];
mypref PREFas[N][2];
int dp[N], a[N], was[N], last[N], k;
int ans = 0;
void calc_sizes(int v, int p) {
  dp[v] = 1;
  for (auto &z : g[v]) {
    if (was[z.first] || z.first == p) continue;
    calc_sizes(z.first, v);
    dp[v] += dp[z.first];
  }
}
int get_centroid(int v, int p, int szz) {
  for (auto &z : g[v]) {
    if (z.first == p || was[z.first]) continue;
    if (dp[z.first] >= szz / 2) return get_centroid(z.first, v, szz);
  }
  return v;
}
void dfs_down(int v, int fi, int lst, int sm, int cost, int p, int tt) {
  add(sm, a[v]);
  if (cost <= k) add(ans, sm);
  if (cost <= k) add(ans, sm);
  cen[v].push_back({cen[p].back()[0], cost, fi, sum(sm, -a[cen[p].back()[0]])});
  pref1[cen[v].back()[0]][fi][tt].xs.push_back({cost, 1});
  prefas[cen[v].back()[0]][fi][tt].xs.push_back({cost, sm});
  PREF1[cen[v].back()[0]][fi].xs.push_back({cost, 1});
  PREFas[cen[v].back()[0]][fi].xs.push_back({cost, sm});
  last[v] = tt;
  for (auto &z : g[v]) {
    if (was[z.first] || z.first == p) continue;
    dfs_down(z.first, fi, z.second, sm, cost + (lst != z.second), v, tt);
  }
}
void get(int v) {
  int j = (int)(cen[v]).size() - 1, id = -1;
  while (1) {
    if (id != -1) {
      int first = cen[v][j][2];
      int me = cen[v][j][3];
      int ce = cen[v][j][0];
      for (int second = 0; second < 2; second++) {
        int how = k - (first != second) - cen[v][j][1];
        int hex = 0;
        add(hex, -mult(me, pref1[ce][second][id].get(how)));
        add(hex, -prefas[ce][second][id].get(how));
        add(hex, mult(me, PREF1[ce][second].get(how)));
        add(hex, PREFas[ce][second].get(how));
        add(ans, hex);
      }
    }
    id = last[cen[v][j][0]];
    j--;
    if (j < 0) break;
  }
}
void build(int v) {
  calc_sizes(v, v);
  v = get_centroid(v, v, dp[v]);
  was[v] = 1;
  cen[v].push_back({v, 0, -1, a[v]});
  int how = 0;
  for (auto &z : g[v])
    if (!was[z.first]) ++how;
  for (int j = 0; j < 2; j++) pref1[v][j].resize(how), prefas[v][j].resize(how);
  how = 0;
  for (auto &z : g[v]) {
    if (was[z.first]) continue;
    dfs_down(z.first, z.second, z.second, a[v], 0, v, how);
    pref1[v][0][how].build();
    pref1[v][1][how].build();
    prefas[v][0][how].build();
    prefas[v][1][how].build();
    ++how;
  }
  PREF1[v][0].build();
  PREF1[v][1].build();
  PREFas[v][0].build();
  PREFas[v][1].build();
  for (auto &z : g[v]) {
    if (!was[z.first]) build(z.first);
  }
}
signed main() {
  INPUT();
  int n;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 1; i < n; i++) {
    int v, u, c;
    cin >> v >> u >> c;
    --v;
    --u;
    g[v].push_back({u, c});
    g[u].push_back({v, c});
  }
  build(0);
  for (int i = 0; i < n; i++) get(i);
  int obr = binpow(2, M - 2);
  ans = mult(ans, obr);
  for (int i = 0; i < n; i++) add(ans, a[i]);
  cout << ans;
  return 0;
}

```