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;
struct C {
  double x, y, r;
};
vector<pair<double, double>> intersect(const C& c1, const C& c2);
struct xy {
  double x, y;
} a[212121];
int n, k;
vector<pair<double, double>> intersect(const C& c1, const C& c2) {
  double x = c1.x - c2.x, y = c1.y - c2.y, r1 = c1.r, r2 = c2.r,
         R = x * x + y * y;
  double d1 = R - (r1 + r2) * (r1 + r2), d2 = R - (r1 - r2) * (r1 - r2);
  if (d1 > 0 || d2 < 0) return {};
  double tx = x * (R - r1 * r1 + r2 * r2), ty = y * (R - r1 * r1 + r2 * r2);
  double t = sqrt(-(double)d1 * (double)d2);
  return {make_pair(c2.x + (tx - y * t) / (2.0L * R),
                    c2.y + (ty + x * t) / (2.0L * R)),
          make_pair(c2.x + (tx + y * t) / (2.0L * R),
                    c2.y + (ty - x * t) / (2.0L * R))};
}
struct point {
  double x, y;
  int col, sa;
};
double ccw(point a, point b, point c) {
  return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
point zero = {0, 0, 0};
double EPS = 1e-14;
int get_sa(point xx) {
  auto [x, y, col, sa] = xx;
  if (x > EPS && -EPS <= y && y <= EPS) return 1;
  if (x > EPS && y > EPS) return 2;
  if (-EPS <= x && x <= EPS && y > EPS) return 3;
  if (x < -EPS && y > EPS) return 4;
  if (x < -EPS && -EPS <= y && y <= EPS) return 5;
  if (x < -EPS && y < -EPS) return 6;
  if (-EPS <= x && x <= EPS && y < -EPS) return 7;
  return 8;
}
bool sort_point(point a, point b) {
  if (a.sa != b.sa) return a.sa < b.sa;
  double c = ccw(zero, a, b);
  if (-EPS <= c && c <= EPS)
    return a.col > b.col;
  else
    return c > EPS;
}
int ck[212121];
int process(double X) {
  int i, j;
  vector<point> L;
  for (i = 0; i < n; i++) {
    ck[i] = 0;
    auto [x, y] = a[i];
    if (x * x + y * y > 4 * X * X) continue;
    C c1, c2;
    c1 = {0, 0, X};
    c2 = {x, y, X};
    auto RES = intersect(c1, c2);
    point p1, p2;
    p1.x = RES[0].first;
    p1.y = RES[0].second;
    p2.x = RES[1].first;
    p2.y = RES[1].second;
    if (ccw(p1, zero, p2) > 0) swap(p1, p2);
    p1.col = +(i + 1);
    p2.col = -(i + 1);
    p1.sa = get_sa(p1);
    p2.sa = get_sa(p2);
    L.push_back(p1);
    L.push_back(p2);
  }
  sort(L.begin(), L.end(), sort_point);
  int now = 0;
  for (auto [x, y, col, sa] : L) {
    int jdc = abs(col);
    if (col < 0 && !ck[jdc]) continue;
    ck[jdc] = 1;
    if (col > 0)
      now++;
    else
      now--;
    if (now >= k) return 1;
  }
  for (auto [x, y, col, sa] : L) {
    int jdc = abs(col);
    if (col < 0 && !ck[jdc]) continue;
    ck[jdc] = 1;
    if (col > 0)
      now++;
    else
      now--;
    if (now >= k) return 1;
  }
  return 0;
}
int main() {
  int i, j;
  double s, e, R;
  scanf("%d%d", &n, &k);
  for (i = 0; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = {(double)x, (double)y};
  }
  s = 0, e = 2e5 + 1;
  for (int i = 0; i <= 50; i++) {
    double m = (s + e) / 2;
    if (process(m)) {
      e = m;
      R = m;
    } else
      s = m;
  }
  printf("%.10lf\n", R);
  return 0;
}
