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
#include <bits/stdc++.h>
using namespace std;
template <class T>
int chkmax(T& a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
int chkmin(T& a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, ostream& out = cerr) {
  while (begin != end) {
    out << (*begin) << " ";
    begin++;
  }
  out << endl;
}
template <class T>
void output(T x, ostream& out = cerr) {
  output(x.begin(), x.end(), out);
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
ostream& operator<<(ostream& os, pair<int, int> pp) {
  return os << pp.first << ' ' << pp.second;
}
const int MOD = 1e9 + 7;
int mul(int a, int b) { return (1LL * a * b) % MOD; }
int diff(int a, int b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
  return a;
}
void subt(int& a, const int& b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}
int sum(int a, int b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
  return a;
}
void add(int& a, const int& b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}
int power(int a, int deg) {
  int res = 1;
  for (; deg; a = mul(a, a), deg >>= 1) {
    if (deg & 1) {
      res = mul(res, a);
    }
  }
  return res;
}
int inverse(int a) { return power(a, MOD - 2); }
int divide(int a, int b) { return mul(a, inverse(b)); }
struct DpHolder {
  int n = 0;
  DpHolder() {}
  deque<pair<int, int>> arr;
  void push(pair<int, int> val) {
    arr.push_front(val);
    n++;
  }
  pair<int, int> prefsum(int pos) {
    pair<int, int> res;
    for (int i = 0; i <= pos && i < arr.size(); ++i) {
      add(res.first, arr[i].first);
      add(res.second, arr[i].second);
    }
    return res;
  }
  void update(int pos, pair<int, int> delta) {
    add(arr[pos].first, delta.first);
    add(arr[pos].second, delta.second);
  }
  pair<int, int> get(int pos) {
    if (pos < 0) {
      return {0, 0};
    }
    return arr[pos];
  }
  void augment(int a) {
    for (int i = 0; i < arr.size(); ++i) {
      add(arr[i].second, mul(arr[i].first, a));
    }
  }
  void print() {
    for (int i = 0; i < arr.size(); ++i) {
      cerr << arr[i].first << ' ' << arr[i].second << '\n';
    }
  }
};
void operator+=(pair<int, int>& a, const pair<int, int>& b) {
  add(a.first, b.first);
  add(a.second, b.second);
}
void operator-=(pair<int, int>& a, const pair<int, int>& b) {
  subt(a.first, b.first);
  subt(a.second, b.second);
}
pair<int, int> operator+(const pair<int, int>& a, const pair<int, int>& b) {
  return {sum(a.first, b.first), sum(a.second, b.second)};
}
pair<int, int> operator-(const pair<int, int>& a, const pair<int, int>& b) {
  return {diff(a.first, b.first), diff(a.second, b.second)};
}
struct DpHolder;
map<DpHolder*, int> storage;
int get_id(DpHolder* ptr) {
  if (storage.find(ptr) == storage.end()) {
    storage[ptr] = storage.size();
  }
  return storage[ptr];
}
DpHolder* add_up(DpHolder* from, DpHolder* to) {
  if (from->n > to->n) {
    swap(from, to);
  }
  for (int i = 0; i < from->n; ++i) {
    to->update(i, from->get(i));
  }
  delete from;
  return to;
}
const int MAX_N = 2e5 + 228;
vector<vector<pair<int, int>>> g;
vector<vector<int>> children;
long long a[MAX_N];
int n, k, up_clr[MAX_N], h[MAX_N];
void hang(int v, int pv) {
  h[v] = 0;
  for (auto [v1, clr] : g[v]) {
    if (v1 != pv) {
      up_clr[v1] = clr;
      children[v].push_back(v1);
      hang(v1, v);
      chkmax(h[v], h[v1] + 1);
    }
  }
  sort(children[v].begin(), children[v].end(),
       [](int u, int v) { return h[u] > h[v]; });
}
void read() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  g.resize(n);
  children.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v, clr;
    cin >> u >> v >> clr;
    u--;
    v--;
    g[u].emplace_back(v, clr);
    g[v].emplace_back(u, clr);
  }
  hang(0, 0);
}
int ans;
DpHolder* dfs(int v) {
  if (children[v].empty()) {
    DpHolder* holder = new DpHolder();
    holder->push({1, a[v]});
    return holder;
  }
  vector<DpHolder*> holders(2);
  holders[0] = dfs(children[v][0]);
  holders[1] = new DpHolder();
  for (int i = 1; i < children[v].size(); ++i) {
    int v1 = children[v][i];
    DpHolder* cur = dfs(v1);
    int type = (up_clr[v1] != up_clr[children[v][0]]);
    for (int cost = 0; cost < cur->n; ++cost) {
      if (cost > k) {
        break;
      }
      pair<int, int> dp_val = cur->get(cost);
      for (int it = 0; it < 2; ++it) {
        int max_cost = k - cost - (type != it);
        if (max_cost >= 0) {
          pair<int, int> other = holders[i]->prefsum(max_cost);
          int delta = 0;
          add(delta, mul(dp_val.first, other.second));
          add(delta, mul(dp_val.second, other.first));
          add(delta, mul(mul(dp_val.first, other.first), a[v]));
          add(ans, delta);
        }
      }
    }
    holders[type] = add_up(cur, holders[type]);
  }
  pair<int, int> v1 = holders[0]->get(min(holders[0]->n - 1, k));
  pair<int, int> v2 = holders[1]->get(min(holders[1]->n - 1, k));
  int delta = 0;
  add(delta, mul(v1.first, a[v]));
  add(delta, v1.second);
  add(delta, mul(v2.first, a[v]));
  add(delta, v2.second);
  add(ans, delta);
  holders[up_clr[v]]->push({0, 0});
  DpHolder* result = add_up(holders[1], holders[0]);
  result->augment(a[v]);
  result->update(0, {1, a[v]});
  return result;
}
void solve() {
  dfs(0);
  for (int i = 0; i < n; ++i) {
    add(ans, a[i]);
  }
  cout << ans << '\n';
}
void test_DP_holder() {
  DpHolder holder;
  holder.push({1, 2});
  holder.push({2, 4});
  cerr << holder.get(0) << '\n';
  cerr << holder.get(1) << '\n';
}
signed main() {
  fast_io();
  read();
  solve();
}
