Soldier's Mission

In this problem, D Country has n cities connected by n - 1 bidirectional roads (forming a tree). C Country is planning a secret attack on D Country. The strategy is to choose s cities from D Country such that they form a connected subgraph, and then to send the top s performing soldiers into these cities.

The cities in the chosen set S each have a danger degree d_i. The assignment is made in the following way: the best soldier is sent to the city with the highest danger degree, the second best soldier is sent to the city with the second highest danger degree, and so on. Access Globe controls the soldier whose performance is the k-th highest. However, if the chosen set has fewer than k cities (i.e. if s < k), then Access Globe will not be deployed and his danger degree is considered 0.

Your task is to calculate the sum of the danger degrees of the city where Access Globe ends up (i.e. the k-th highest danger degree from the chosen set) over all possible choices of a connected set of exactly s cities. Since this sum can be large, output it modulo \(64\,123\). All valid sets are chosen uniformly, and you need to sum the value over all possible sets.

Note: If \(s < k\), then every valid set yields a danger degree of 0 for Access Globe.

Formally, if a connected set \(S\) of exactly \(s\) cities has danger degrees \(d_{i_1}, d_{i_2}, \dots, d_{i_s}\) (not necessarily sorted), sort them in non-increasing order as \(a_1 \ge a_2 \ge \dots \ge a_s\). Then the contribution of this set is \(a_k\) (or 0 if \(s < k\)). Compute the sum of contributions for all connected sets \(S\) of size \(s\), and output the answer modulo 64,123.

inputFormat

The first line contains three integers n, s, and k (1 ≤ n ≤ 15 for this problem, and other parameters satisfy 1 ≤ s ≤ n and 1 ≤ k ≤ s).

The second line contains n integers \(d_1, d_2, \dots, d_n\) where \(d_i\) represents the danger degree of city \(i\).

Each of the next n - 1 lines contains two integers u and v describing a bidirectional road between cities u and v (cities are 1-indexed).

outputFormat

Output a single integer, the sum over all valid connected subsets of exactly s cities of the danger degree at the k-th highest city (or 0 if \(s < k\)), taken modulo \(64\,123\).

sample

3 2 1
5 3 4
1 2
2 3

9