Access Globe is currently playing a strategy game. In the game, the character he controls is a soldier from Country C. His task is to obey the commander's orders to participate in battles and win.

Country C is about to launch a secret attack on Country D. The operation plan is as follows: choose $s$ cities in Country D and send the $s$ soldiers from Country C with the highest performance records to infiltrate these cities respectively. Each city has a danger level $d_i$. The commander of Country C will send the soldier with the highest performance record to the city with the highest danger level among the chosen cities, the soldier with the second-highest performance record to the city with the second-highest danger level among the chosen cities, and so on (i.e., send the soldier with the $i$-th highest performance record to the city with the $i$-th highest danger level among the chosen cities). Country D has $n$ cities and $n-1$ bidirectional roads connecting these cities, such that all cities are reachable from each other. For the mission to be executed successfully, any two chosen cities must be reachable from each other without passing through any unchosen cities.

The performance record of the soldier controlled by Access Globe is the $k$-th highest. He hopes to estimate the danger level of the city he will eventually infiltrate. Access Globe assumes that Country C chooses any set of cities $S$ that satisfies the conditions with equal probability. He wants you to help him calculate the sum of the danger levels of the cities infiltrated by the soldier controlled by Access Globe across all possible city sets. If fewer than $k$ cities are chosen, Access Globe will not be dispatched, and in this case, the danger level is 0.

Of course, you do not want to help him solve this problem, nor do you intend to tell him the remainder of this value divided by $998,244,353$. You only intend to tell him the remainder of this value divided by $64,123$.

Input

The first line contains 3 integers $n, k, W$, representing the number of cities in Country D, the performance rank of the soldier controlled by Access Globe, and the maximum danger level among all cities in Country D.

The second line contains $n$ integers between $1$ and $W$, $d_1, d_2, \dots, d_n$, representing the danger level of each city.

From the third line to the $n+1$-th line, each line contains two integers $x_i, y_i$, representing a bidirectional road connecting city $x_i$ and city $y_i$ in Country D.

Output

Output a single integer representing the sum of the danger levels of the cities infiltrated by the soldier controlled by Access Globe across all feasible city sets, modulo $64,123$.

Examples

Input 1

5 3 3
2 1 1 2 3
1 2
2 3
1 4
1 5

Output 1

11

Note 1

The map of Country D is as follows, where a city with danger level $d$ is represented by a $(d+3)$-sided polygon.

The following are all valid schemes where at least 3 cities are chosen: Choose cities 1, 2, 3, the danger level of the city infiltrated by Access Globe's soldier is 1; Choose cities 1, 2, 3, 4, the danger level of the city infiltrated by Access Globe's soldier is 1; Choose cities 1, 2, 3, 5, the danger level of the city infiltrated by Access Globe's soldier is 1; Choose cities 1, 2, 3, 4, 5, the danger level of the city infiltrated by Access Globe's soldier is 2; Choose cities 1, 2, 4, the danger level of the city infiltrated by Access Globe's soldier is 1; Choose cities 1, 2, 5, the danger level of the city infiltrated by Access Globe's soldier is 1; Choose cities 1, 2, 4, 5, the danger level of the city infiltrated by Access Globe's soldier is 2; Choose cities 1, 4, 5, the danger level of the city infiltrated by Access Globe's soldier is 2; while for cases with fewer than 3 cities chosen, the danger level is 0; Therefore, you should output $(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) \pmod{64,123} = 11$.

Input 2

10 2 3
2 1 1 3 1 2 3 3 1 3
1 2
2 3
2 4
2 5
2 6
5 7
1 8
8 9
1 10

Output 2

435

Subtasks

For all data, $1 \le k \le n$, $1 \le d_i \le W$, $n, k, W \le 1,666$.