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 \leq u \leq v \leq n\)) that does not need more than \(k\) tickets, modulo \(10^9 + 7\).
Output
Output an integer denoting the total happiness value for all valid tours \((u, v)\) (\(1 \leq u \leq v \leq n\)), modulo \(10^9 + 7\).