Problem Background

We could have had it all...

We were meant to have everything...

Counting on a tree...

Why resort to counting on a tree...

Counting on a Tree (CoaT) is the English name for this problem.

Problem Description

Access Globe has recently been playing a strategic game. In the game, the character he controls is a soldier from country C. His mission is to follow the commander's orders to engage in battles and secure victories.

Country C is about to launch a secret assault on country D. The battle plan is as follows: Select $s$ cities in country D and dispatch the top $s$ soldiers from country C to infiltrate these cities secretly. Each city has a danger level $d_i$.

The commander of country C will send the highest-ranking soldier to the city with the highest danger level among the selected cities, the second-highest-ranking soldier to the city with the second-highest danger level, and so on (i.e., the $i$-th highest-ranking soldier to the city with the $i$-th highest danger level). Country D has $n$ cities connected by $n - 1$ bidirectional roads, ensuring that any two cities can reach each other. To ensure the smooth execution of the mission, the $s$ cities chosen by country C must be such that any two of them can be reached from each other without passing through unselected cities.

Access Globe controls the soldier who ranks $k$-th in terms of combat effectiveness. He wants to estimate the danger level of the city he will infiltrate. Access Globe assumes that country C selects any eligible set of cities $S$ with equal probability. He wants you to calculate the sum of the danger levels of the cities he might infiltrate 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 don't want to help him solve this problem, nor do you plan to tell him the value modulo $998,244,353$. You only plan to tell him the value modulo $64,123$.

Input Format

The first line contains three integers $n, k, W$, representing the number of cities in country D, the rank of Access Globe's soldier in terms of combat effectiveness, and the maximum danger level among all cities in country D.

The second line contains $n$ integers $d_1, d_2, \ldots, d_n$, representing the danger levels of each city, ranging from $1$ to $W$.

From the third line to the $(n + 1)$-th line, each line contains two integers $x_i, y_i$, indicating that there is a bidirectional road connecting city $x_i$ and city $y_i$ in country D.

Output Format

Output a single integer, which is the sum of the danger levels of the cities Access Globe's soldier might infiltrate across all feasible city sets, modulo $64,123$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

11

Sample 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

Sample Output #2

435

Notes

The map of country D is as follows, where cities with danger level $d$ are shaped like $d + 3$-sided polygons.

The following are all valid plans with at least 3 cities selected:

• Selecting cities $1, 2, 3$, Access Globe's soldier infiltrates a city with danger level $1$;
• Selecting cities $1, 2, 3, 4$, Access Globe's soldier infiltrates a city with danger level $1$;
• Selecting cities $1, 2, 3, 5$, Access Globe's soldier infiltrates a city with danger level $1$;
• Selecting cities $1, 2, 3, 4, 5$, Access Globe's soldier infiltrates a city with danger level $2$;
• Selecting cities $1, 2, 4$, Access Globe's soldier infiltrates a city with danger level $1$;
• Selecting cities $1, 2, 5$, Access Globe's soldier infiltrates a city with danger level $1$;
• Selecting cities $1, 2, 4, 5$, Access Globe's soldier infiltrates a city with danger level $2$;
• Selecting cities $1, 4, 5$, Access Globe's soldier infiltrates a city with danger level $2$;
• When fewer than 3 cities are selected, the danger level for Access Globe's soldier is $0$.

Thus, you should output $(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) \bmod 64,123 = 11$.

见题面 Input 部分

见题面 Output 部分