#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 200010;
int c[2][N][2];
int lowbit(int x) { return x & (-x); }
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void add(int id, int x, int y) {
  x++;
  for (int i = x; i < N; i += lowbit(i)) {
    add(c[id][i][0], y);
    add(c[id][i][1], 1);
  }
}
pair<int, int> query(int id, int x) {
  x++;
  int sum = 0, tot = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    add(sum, c[id][i][0]);
    add(tot, c[id][i][1]);
  }
  return make_pair(sum, tot);
}
void unset(int id, int x) {
  x++;
  for (int i = x; i < N; i += lowbit(i)) c[id][i][0] = c[id][i][1] = 0;
}
int max_dis;
int a[N];
vector<int> v[N], w[N];
pair<int, int> pt[N];
bool visit[N];
int sz[N], msz[N], cnt;
void dfs(int u, int fa) {
  sz[u] = 1;
  msz[u] = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first != fa && !visit[first]) {
      dfs(first, u);
      sz[u] += sz[first];
      msz[u] = max(msz[u], sz[first]);
    }
  }
  pt[cnt++] = make_pair(u, msz[u]);
}
int get_center(int u) {
  cnt = 0;
  dfs(u, 0);
  int ans = 0, mi = 0x7fffffff;
  int sum = sz[u];
  for (int i = 0; i < cnt; i++) {
    pt[i].second = max(pt[i].second, sum - pt[i].second);
    if (pt[i].second < mi) {
      mi = pt[i].second;
      ans = pt[i].first;
    }
  }
  return ans;
}
int ans;
int root_val;
struct point {
  int cost, col;
  long long sum;
  point() {}
  point(int cost, int col, long long sum) : cost(cost), col(col), sum(sum) {}
} records[N];
int cc;
void dfs(int u, int fa, int cost, int col, long long sum, int old_col) {
  if (cost > max_dis) return;
  add(ans, sum % mod);
  pair<int, int> t = query(old_col, max_dis - cost);
  add(ans, t.first);
  add(ans, 1LL * (sum - root_val) % mod * t.second % mod);
  if (cost < max_dis) {
    t = query(old_col ^ 1, max_dis - cost - 1);
    add(ans, t.first);
    add(ans, 1LL * (sum - root_val) % mod * t.second % mod);
  }
  records[++cc] = point(cost, old_col, sum);
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first == fa || visit[first]) continue;
    dfs(first, u, cost + (col != w[u][i]), w[u][i], sum + a[first], old_col);
  }
}
void cal(int u) {
  root_val = a[u];
  cc = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (visit[first]) continue;
    int pre = cc;
    dfs(first, u, 0, w[u][i], a[u] + a[first], w[u][i]);
    for (int j = pre + 1; j <= cc; j++) {
      add(records[j].col, records[j].cost, records[j].sum % mod);
    }
  }
  for (int j = 1; j <= cc; j++) unset(records[j].col, records[j].cost);
  visit[u] = true;
  add(ans, a[u]);
}
void solve(int u, int fa) {
  u = get_center(u);
  cal(u);
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first != fa && !visit[first]) solve(first, u);
  }
}
int main() {
  int n;
  scanf("%d%d", &n, &max_dis);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z);
    v[first].push_back(second);
    w[first].push_back(z);
    v[second].push_back(first);
    w[second].push_back(z);
  }
  solve(1, 0);
  cout << ans << endl;
  return 0;
}

### Prompt

Create a solution in CPP for 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;
const int mod = 1000000007;
const int N = 200010;
int c[2][N][2];
int lowbit(int x) { return x & (-x); }
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
void add(int id, int x, int y) {
  x++;
  for (int i = x; i < N; i += lowbit(i)) {
    add(c[id][i][0], y);
    add(c[id][i][1], 1);
  }
}
pair<int, int> query(int id, int x) {
  x++;
  int sum = 0, tot = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    add(sum, c[id][i][0]);
    add(tot, c[id][i][1]);
  }
  return make_pair(sum, tot);
}
void unset(int id, int x) {
  x++;
  for (int i = x; i < N; i += lowbit(i)) c[id][i][0] = c[id][i][1] = 0;
}
int max_dis;
int a[N];
vector<int> v[N], w[N];
pair<int, int> pt[N];
bool visit[N];
int sz[N], msz[N], cnt;
void dfs(int u, int fa) {
  sz[u] = 1;
  msz[u] = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first != fa && !visit[first]) {
      dfs(first, u);
      sz[u] += sz[first];
      msz[u] = max(msz[u], sz[first]);
    }
  }
  pt[cnt++] = make_pair(u, msz[u]);
}
int get_center(int u) {
  cnt = 0;
  dfs(u, 0);
  int ans = 0, mi = 0x7fffffff;
  int sum = sz[u];
  for (int i = 0; i < cnt; i++) {
    pt[i].second = max(pt[i].second, sum - pt[i].second);
    if (pt[i].second < mi) {
      mi = pt[i].second;
      ans = pt[i].first;
    }
  }
  return ans;
}
int ans;
int root_val;
struct point {
  int cost, col;
  long long sum;
  point() {}
  point(int cost, int col, long long sum) : cost(cost), col(col), sum(sum) {}
} records[N];
int cc;
void dfs(int u, int fa, int cost, int col, long long sum, int old_col) {
  if (cost > max_dis) return;
  add(ans, sum % mod);
  pair<int, int> t = query(old_col, max_dis - cost);
  add(ans, t.first);
  add(ans, 1LL * (sum - root_val) % mod * t.second % mod);
  if (cost < max_dis) {
    t = query(old_col ^ 1, max_dis - cost - 1);
    add(ans, t.first);
    add(ans, 1LL * (sum - root_val) % mod * t.second % mod);
  }
  records[++cc] = point(cost, old_col, sum);
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first == fa || visit[first]) continue;
    dfs(first, u, cost + (col != w[u][i]), w[u][i], sum + a[first], old_col);
  }
}
void cal(int u) {
  root_val = a[u];
  cc = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (visit[first]) continue;
    int pre = cc;
    dfs(first, u, 0, w[u][i], a[u] + a[first], w[u][i]);
    for (int j = pre + 1; j <= cc; j++) {
      add(records[j].col, records[j].cost, records[j].sum % mod);
    }
  }
  for (int j = 1; j <= cc; j++) unset(records[j].col, records[j].cost);
  visit[u] = true;
  add(ans, a[u]);
}
void solve(int u, int fa) {
  u = get_center(u);
  cal(u);
  for (int i = 0; i < v[u].size(); i++) {
    int first = v[u][i];
    if (first != fa && !visit[first]) solve(first, u);
  }
}
int main() {
  int n;
  scanf("%d%d", &n, &max_dis);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z);
    v[first].push_back(second);
    w[first].push_back(z);
    v[second].push_back(first);
    w[second].push_back(z);
  }
  solve(1, 0);
  cout << ans << endl;
  return 0;
}

```