#include <bits/stdc++.h>
using namespace std;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
const double eps = 1e-8;
const double pi = acosl(-1.0);
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  long long n;
  modint() : n(0) { ; }
  modint(long long m) : n(m) {
    if (n >= mod)
      n %= mod;
    else if (n < 0)
      n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 2;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
using mP = pair<modint, modint>;
struct Data {
  int t, col;
  modint sum;
};
modint ans = 0;
int K;
vector<int> a;
struct edge {
  int to, col;
};
const int mn = 1 << 18;
vector<edge> G[mn];
queue<vector<int>> q;
bool exi[mn];
void yaru(vector<int> v) {
  if (v.empty()) return;
  for (int id : v) exi[id] = true;
  int g;
  int sz = v.size();
  function<int(int, int)> s_root = [&](int id, int fr) -> int {
    int res = 1;
    int ma = 0;
    for (edge e : G[id]) {
      if (e.to == fr) continue;
      if (!exi[e.to]) continue;
      int nex = s_root(e.to, id);
      ma = max(ma, nex);
      res += nex;
    }
    if (ma <= sz / 2 && sz - res <= sz / 2) g = id;
    return res;
  };
  s_root(v[0], -1);
  vector<mP> psum[2];
  vector<vector<mP>> sum[2];
  vector<vector<Data>> datas;
  modint csum = 0;
  for (edge e : G[g])
    if (exi[e.to]) {
      int tmp = datas.size();
      datas.push_back({});
      function<void(int, int, Data)> dfs = [&](int id, int fr, Data d) {
        if (!exi[id]) return;
        datas[tmp].push_back({d.t, e.col, d.sum});
        for (edge e : G[id]) {
          if (e.to == fr) continue;
          Data nd = d;
          if (d.col != e.col) nd.t++;
          nd.col = e.col;
          nd.sum += a[e.to];
          dfs(e.to, id, nd);
        }
      };
      dfs(e.to, g, {0, e.col, a[e.to]});
    }
  auto add = [&](vector<mP>& v, mP p, int loc) {
    while (v.size() <= loc) v.push_back({0, 0});
    v[loc].first += p.first;
    v[loc].second += p.second;
  };
  auto matome = [&](vector<mP>& v) {
    for (int i = 0; i < (int)v.size(); i++)
      if (i > 0) {
        v[i].first += v[i - 1].first;
        v[i].second += v[i - 1].second;
      }
  };
  for (int j = 0; j < 2; j++) {
    sum[j].resize(datas.size());
  }
  for (int i = 0; i < datas.size(); i++) {
    for (Data d : datas[i]) {
      if (d.t <= K) {
        csum += (modint)2 * (d.sum + (modint)a[g]);
      }
      add(psum[d.col], {d.sum, 1}, d.t);
      add(sum[d.col][i], {d.sum, 1}, d.t);
    }
  }
  for (int j = 0; j < 2; j++) {
    matome(psum[j]);
    for (int i = 0; i < datas.size(); i++) {
      matome(sum[j][i]);
    }
  }
  for (int i = 0; i < datas.size(); i++) {
    for (Data d : datas[i]) {
      for (int j = 0; j < 2; j++) {
        int sup = K - d.t;
        if (j != d.col) sup--;
        if (sup >= 0) {
          modint val = 0;
          if (psum[j].size()) {
            int loc = min(sup, (int)psum[j].size() - 1);
            int cnt = psum[j][loc].second;
            val += (d.sum + (modint)a[g]) * (modint)cnt + psum[j][loc].first;
          }
          if (sum[j][i].size()) {
            int loc = min(sup, (int)sum[j][i].size() - 1);
            int cnt = sum[j][i][loc].second;
            val -= (d.sum + (modint)a[g]) * (modint)cnt + sum[j][i][loc].first;
            assert(psum[j].size());
          }
          csum += val;
        }
      }
    }
  }
  ans += csum;
  vector<vector<int>> chs;
  vector<int> nexs;
  function<void(int, int)> search_next = [&](int id, int fr) {
    if (!exi[id]) return;
    nexs.push_back(id);
    for (edge e : G[id]) {
      if (e.to == fr) continue;
      search_next(e.to, id);
    }
  };
  for (edge e : G[g]) {
    search_next(e.to, g);
    if (nexs.empty()) continue;
    q.push(nexs);
    chs.push_back(nexs);
    nexs.clear();
  }
  for (int id : v) exi[id] = false;
}
void uoo(int n) {
  vector<int> ori(n);
  for (int i = 0; i < n; i++) ori[i] = i;
  q.push(ori);
  while (!q.empty()) {
    vector<int> v = q.front();
    q.pop();
    yaru(v);
  }
}
void solve() {
  int n;
  cin >> n >> K;
  a.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  uoo(n);
  ans /= 2;
  for (int i = 0; i < n; i++) ans += a[i];
  cout << ans << "\n";
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

### Prompt

Your challenge is to write 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;
constexpr long long mod = 1000000007;
const long long INF = mod * mod;
const double eps = 1e-8;
const double pi = acosl(-1.0);
long long mod_pow(long long x, long long n, long long m = mod) {
  if (n < 0) {
    long long res = mod_pow(x, -n, m);
    return mod_pow(res, m - 2, m);
  }
  if (abs(x) >= m) x %= m;
  if (x < 0) x += m;
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return res;
}
struct modint {
  long long n;
  modint() : n(0) { ; }
  modint(long long m) : n(m) {
    if (n >= mod)
      n %= mod;
    else if (n < 0)
      n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod) a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0) a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((long long)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, long long n) {
  if (n == 0) return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
long long inv(long long a, long long p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}
const int max_n = 1 << 2;
modint fact[max_n], factinv[max_n];
void init_f() {
  fact[0] = modint(1);
  for (int i = 0; i < max_n - 1; i++) {
    fact[i + 1] = fact[i] * modint(i + 1);
  }
  factinv[max_n - 1] = modint(1) / fact[max_n - 1];
  for (int i = max_n - 2; i >= 0; i--) {
    factinv[i] = factinv[i + 1] * modint(i + 1);
  }
}
modint comb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;
  return fact[a] * factinv[a - b];
}
using mP = pair<modint, modint>;
struct Data {
  int t, col;
  modint sum;
};
modint ans = 0;
int K;
vector<int> a;
struct edge {
  int to, col;
};
const int mn = 1 << 18;
vector<edge> G[mn];
queue<vector<int>> q;
bool exi[mn];
void yaru(vector<int> v) {
  if (v.empty()) return;
  for (int id : v) exi[id] = true;
  int g;
  int sz = v.size();
  function<int(int, int)> s_root = [&](int id, int fr) -> int {
    int res = 1;
    int ma = 0;
    for (edge e : G[id]) {
      if (e.to == fr) continue;
      if (!exi[e.to]) continue;
      int nex = s_root(e.to, id);
      ma = max(ma, nex);
      res += nex;
    }
    if (ma <= sz / 2 && sz - res <= sz / 2) g = id;
    return res;
  };
  s_root(v[0], -1);
  vector<mP> psum[2];
  vector<vector<mP>> sum[2];
  vector<vector<Data>> datas;
  modint csum = 0;
  for (edge e : G[g])
    if (exi[e.to]) {
      int tmp = datas.size();
      datas.push_back({});
      function<void(int, int, Data)> dfs = [&](int id, int fr, Data d) {
        if (!exi[id]) return;
        datas[tmp].push_back({d.t, e.col, d.sum});
        for (edge e : G[id]) {
          if (e.to == fr) continue;
          Data nd = d;
          if (d.col != e.col) nd.t++;
          nd.col = e.col;
          nd.sum += a[e.to];
          dfs(e.to, id, nd);
        }
      };
      dfs(e.to, g, {0, e.col, a[e.to]});
    }
  auto add = [&](vector<mP>& v, mP p, int loc) {
    while (v.size() <= loc) v.push_back({0, 0});
    v[loc].first += p.first;
    v[loc].second += p.second;
  };
  auto matome = [&](vector<mP>& v) {
    for (int i = 0; i < (int)v.size(); i++)
      if (i > 0) {
        v[i].first += v[i - 1].first;
        v[i].second += v[i - 1].second;
      }
  };
  for (int j = 0; j < 2; j++) {
    sum[j].resize(datas.size());
  }
  for (int i = 0; i < datas.size(); i++) {
    for (Data d : datas[i]) {
      if (d.t <= K) {
        csum += (modint)2 * (d.sum + (modint)a[g]);
      }
      add(psum[d.col], {d.sum, 1}, d.t);
      add(sum[d.col][i], {d.sum, 1}, d.t);
    }
  }
  for (int j = 0; j < 2; j++) {
    matome(psum[j]);
    for (int i = 0; i < datas.size(); i++) {
      matome(sum[j][i]);
    }
  }
  for (int i = 0; i < datas.size(); i++) {
    for (Data d : datas[i]) {
      for (int j = 0; j < 2; j++) {
        int sup = K - d.t;
        if (j != d.col) sup--;
        if (sup >= 0) {
          modint val = 0;
          if (psum[j].size()) {
            int loc = min(sup, (int)psum[j].size() - 1);
            int cnt = psum[j][loc].second;
            val += (d.sum + (modint)a[g]) * (modint)cnt + psum[j][loc].first;
          }
          if (sum[j][i].size()) {
            int loc = min(sup, (int)sum[j][i].size() - 1);
            int cnt = sum[j][i][loc].second;
            val -= (d.sum + (modint)a[g]) * (modint)cnt + sum[j][i][loc].first;
            assert(psum[j].size());
          }
          csum += val;
        }
      }
    }
  }
  ans += csum;
  vector<vector<int>> chs;
  vector<int> nexs;
  function<void(int, int)> search_next = [&](int id, int fr) {
    if (!exi[id]) return;
    nexs.push_back(id);
    for (edge e : G[id]) {
      if (e.to == fr) continue;
      search_next(e.to, id);
    }
  };
  for (edge e : G[g]) {
    search_next(e.to, g);
    if (nexs.empty()) continue;
    q.push(nexs);
    chs.push_back(nexs);
    nexs.clear();
  }
  for (int id : v) exi[id] = false;
}
void uoo(int n) {
  vector<int> ori(n);
  for (int i = 0; i < n; i++) ori[i] = i;
  q.push(ori);
  while (!q.empty()) {
    vector<int> v = q.front();
    q.pop();
    yaru(v);
  }
}
void solve() {
  int n;
  cin >> n >> K;
  a.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  uoo(n);
  ans /= 2;
  for (int i = 0; i < n; i++) ans += a[i];
  cout << ans << "\n";
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

```