B'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 <= q u <= q v <= q n ) that does not need more than k tickets, modulo 10^9 + 7 . The first line contains two integers n and k ( 2 <= q n <= q 2 cdot 10^5 , 0 <= q k <= q 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, ldots, a_n ( 0 <= q a_i <= q 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 <= q u_i, v_i <= q n , 0 <= q t_i <= q 1 ) -- an edge between vertices u_i and v_i with color t_i . The given edges form a tree. Output an integer denoting the total happiness value for all valid tours (u, v) ( 1 <= q u <= q v <= q n ), modulo 10^9 + 7 . '...