#include <bits/stdc++.h>
using namespace std;
int Size[200005];
vector<pair<int, int> > v[200005];
int forbid[200005];
vector<int> tmp;
void dfs(int first, int f) {
  Size[first] = 1;
  tmp.push_back(first);
  for (auto it : v[first]) {
    if (it.first != f && !forbid[it.first]) {
      dfs(it.first, first);
      Size[first] += Size[it.first];
    }
  }
}
int cen(int first) {
  tmp.clear();
  dfs(first, 0);
  int xx = Size[first];
  int res = 0;
  for (auto it : tmp) {
    if (Size[it] >= (xx + 1) / 2) {
      res = it;
    }
  }
  return res;
}
long long S[4][200005];
const int mod = 1e9 + 7;
void add(int first, int k, long long *s) {
  first++;
  for (int i = first; i < 200005; i += i & -i) {
    s[i] += k;
    s[i] %= mod;
  }
}
void reset(int first, long long *s) {
  first++;
  for (int i = first; i < 200005; i += i & -i) {
    s[i] = 0;
  }
}
long long query(int first, long long *s) {
  first++;
  long long res = 0;
  for (int i = first; i > 0; i -= i & -i) {
    res += s[i];
    res %= mod;
  }
  return res;
}
vector<pair<long long, long long> > vv;
long long a[200005];
void dfs(int first, int last, int f, int sum, long long sum2) {
  vv.push_back(make_pair(a[first] + sum2, sum));
  for (auto it : v[first]) {
    if (it.first != f && !forbid[it.first]) {
      dfs(it.first, it.second, first, sum + (it.second != last),
          (sum2 + a[first]) % mod);
    }
  }
}
long long ans = 0;
int k;
vector<pair<int, int> > ttmp;
void go(int first) {
  first = cen(first);
  for (auto it : v[first]) {
    if (!forbid[it.first]) {
      dfs(it.first, it.second, first, 0, a[first]);
      for (auto it2 : vv) {
        ans += query(k - it2.second, S[it.second]);
        ans += query(k - it2.second, S[2 + it.second]) * it2.first % mod;
        ans += query(k - it2.second - 1, S[it.second ^ 1]);
        ans +=
            query(k - it2.second - 1, S[2 + (it.second ^ 1)]) * it2.first % mod;
        if (it2.second <= k) ans += it2.first;
        ans %= mod;
      }
      for (auto it2 : vv) {
        add(it2.second, it2.first - a[first], S[it.second]);
        add(it2.second, 1, S[2 + it.second]);
        ttmp.push_back(it2);
      }
      vv.clear();
    }
  }
  for (auto it : ttmp) {
    reset(it.second, S[0]);
    reset(it.second, S[1]);
    reset(it.second, S[2]);
    reset(it.second, S[3]);
  }
  ttmp.clear();
  forbid[first] = 1;
  for (auto it : v[first]) {
    if (!forbid[it.first]) {
      go(it.first);
    }
  }
}
void solve() {
  int n;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans += a[i];
  for (int i = 1; i < n; i++) {
    int first, second, w;
    scanf("%d %d %d", &first, &second, &w);
    v[first].push_back(make_pair(second, w));
    v[second].push_back(make_pair(first, w));
  }
  go(1);
  printf("%lld\n", (ans % mod + mod) % mod);
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  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;
int Size[200005];
vector<pair<int, int> > v[200005];
int forbid[200005];
vector<int> tmp;
void dfs(int first, int f) {
  Size[first] = 1;
  tmp.push_back(first);
  for (auto it : v[first]) {
    if (it.first != f && !forbid[it.first]) {
      dfs(it.first, first);
      Size[first] += Size[it.first];
    }
  }
}
int cen(int first) {
  tmp.clear();
  dfs(first, 0);
  int xx = Size[first];
  int res = 0;
  for (auto it : tmp) {
    if (Size[it] >= (xx + 1) / 2) {
      res = it;
    }
  }
  return res;
}
long long S[4][200005];
const int mod = 1e9 + 7;
void add(int first, int k, long long *s) {
  first++;
  for (int i = first; i < 200005; i += i & -i) {
    s[i] += k;
    s[i] %= mod;
  }
}
void reset(int first, long long *s) {
  first++;
  for (int i = first; i < 200005; i += i & -i) {
    s[i] = 0;
  }
}
long long query(int first, long long *s) {
  first++;
  long long res = 0;
  for (int i = first; i > 0; i -= i & -i) {
    res += s[i];
    res %= mod;
  }
  return res;
}
vector<pair<long long, long long> > vv;
long long a[200005];
void dfs(int first, int last, int f, int sum, long long sum2) {
  vv.push_back(make_pair(a[first] + sum2, sum));
  for (auto it : v[first]) {
    if (it.first != f && !forbid[it.first]) {
      dfs(it.first, it.second, first, sum + (it.second != last),
          (sum2 + a[first]) % mod);
    }
  }
}
long long ans = 0;
int k;
vector<pair<int, int> > ttmp;
void go(int first) {
  first = cen(first);
  for (auto it : v[first]) {
    if (!forbid[it.first]) {
      dfs(it.first, it.second, first, 0, a[first]);
      for (auto it2 : vv) {
        ans += query(k - it2.second, S[it.second]);
        ans += query(k - it2.second, S[2 + it.second]) * it2.first % mod;
        ans += query(k - it2.second - 1, S[it.second ^ 1]);
        ans +=
            query(k - it2.second - 1, S[2 + (it.second ^ 1)]) * it2.first % mod;
        if (it2.second <= k) ans += it2.first;
        ans %= mod;
      }
      for (auto it2 : vv) {
        add(it2.second, it2.first - a[first], S[it.second]);
        add(it2.second, 1, S[2 + it.second]);
        ttmp.push_back(it2);
      }
      vv.clear();
    }
  }
  for (auto it : ttmp) {
    reset(it.second, S[0]);
    reset(it.second, S[1]);
    reset(it.second, S[2]);
    reset(it.second, S[3]);
  }
  ttmp.clear();
  forbid[first] = 1;
  for (auto it : v[first]) {
    if (!forbid[it.first]) {
      go(it.first);
    }
  }
}
void solve() {
  int n;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans += a[i];
  for (int i = 1; i < n; i++) {
    int first, second, w;
    scanf("%d %d %d", &first, &second, &w);
    v[first].push_back(make_pair(second, w));
    v[second].push_back(make_pair(first, w));
  }
  go(1);
  printf("%lld\n", (ans % mod + mod) % mod);
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}

```