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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define kyou using
#define mo namespace
#define kawaii std
#define chisai chrono
#define dekai __gnu_pbds;

kyou mo kawaii;
kyou mo chisai;
kyou mo dekai;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define endl "\n"
#define ohamachi cin.tie(0) -> sync_with_stdio(0)
#define otsumachi exit(0)
#define ll long long
#define ld double
const int MX = 200005;
const int LG = 30;
const int BLOCK = 330;
const int inf = 1e9 + 69;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2ll;
const ll infll = 4e18 + 6969;
const short dx[] = {0, 1, 0, -1};
const short dy[] = {1, 0, -1, 0};
const ld eps = 1e-6;

class timer: high_resolution_clock{
	const time_point start_time;
public:
	timer():start_time(now()){}
	rep elapsed_time() const{ 
		return duration_cast<milliseconds>(now() - start_time).count(); 
 	}
};

int n, k, sz[MX], wt[MX];
vector<pair<int, int> > adj[MX];
bitset<MX> used;
ll ans = 0ll;

void dfs_sz(int nw, int bf){
	sz[nw] = 1;
	for(auto nx : adj[nw]) if(nx.first != bf && !used[nx.first]){
		dfs_sz(nx.first, nw);
		sz[nw] += sz[nx.first];
	}
}

int get_centroid(int nw){
	dfs_sz(nw, nw);

	int szt = sz[nw] / 2;
	for(bool f = 0; !f;){
		f = 1;
		for(auto nx : adj[nw]) if(!used[nx.first] && sz[nx.first] <= sz[nw])
			if(sz[nx.first] > szt / 2){
				f = 0;
				nw = nx.first; break;
			}
	}

	return nw;
}

struct BIT{
	pair<ll, ll> fwt[MX];
	void clear(){
		memset(fwt, 0, sizeof(fwt));
	}

	void upd(int ps, pair<ll, ll> val){
		for(ps ++; ps < MX; ps += ps & -ps){
			(fwt[ps].first += val.first) %= mod;
			if(fwt[ps].first < 0) fwt[ps].first += mod;
			fwt[ps].second += val.second;
		}
	}
	pair<ll, ll> que(int ps){
		pair<ll, ll> r = {0, 0};
		for(ps ++; ps > 0; ps -= ps & -ps){
			(r.first += fwt[ps].first) %= mod;
			if(r.first < 0) r.first += mod;
			r.second += fwt[ps].second;
		}
		return r;
	}
} fwt[2];

void solve(int nw = 1){
	nw = get_centroid(nw);
	int cent = nw;

	vector<pair<ll, pair<ll, ll> > > op;
	for(auto nx : adj[nw]) if(!used[nx.first]){
		vector<pair<int, int> > candidates;

		function <void(int, int, int, int, ll)> dfs = [&](int nw, int bf, int cl, int dp, ll wtg){
			if(dp <= k) (ans += wtg + wt[cent]) %= mod;
			candidates.push_back({dp, wtg});
			for(auto nx : adj[nw]) if(nx.first != bf && !used[nx.first])
				dfs(nx.first, nw, nx.second, dp + (cl != nx.second), wtg + wt[nx.first]);
		};

		dfs(nx.first, nw, nx.second, 0, wt[nx.first]);
		for(auto e : candidates){
			if(k >= e.first){
				pair<ll, ll> tmp = fwt[nx.second].que(k - e.first);
				(ans += tmp.first) %= mod;
				(ans += (tmp.second * 1ll * ((e.second + wt[nw]) % mod)) % mod) %= mod;
			}
			if(k >= e.first + 1){
				pair<ll, ll> tmp = fwt[1 - nx.second].que(k - e.first - 1);
				(ans += tmp.first) %= mod;
				(ans += (tmp.second * 1ll * ((e.second + wt[nw]) % mod)) % mod) %= mod;
			}
		}

		for(auto e : candidates){
			fwt[nx.second].upd(e.first, {e.second, 1});
			op.push_back({e.first, {e.second, nx.second}});
		}
	}

	for(auto i : op)
		fwt[i.second.second].upd(i.first, {-i.second.first, -1});

	used[nw] = 1;
	for(auto nx : adj[nw]) if(!used[nx.first])
		solve(nx.first);
}

int main(){
	ohamachi;

	cin >> n >> k;
	for(int i = 1; i <= n; i ++){
		cin >> wt[i];
		(ans += wt[i]) %= mod;
	}
	for(int u, v, w, i = 1; i < n; i ++){
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	solve();
	cout << ans << endl;
	
	otsumachi;
}