Description

Sulawesi. There are still $L$ units of time before Earth enters Jupiter's Roche limit.

Cai Deren received from Alifen the "Ignite Jupiter Plan". The plan requires him to gather all nearby rescue teams at the same steering engine, clear obstacles, and use the "Spring Festival Twelve Bangs" program to control the engine to ignite Jupiter.

There are $n$ steering engines in total, connected by $n - 1$ roads. Any two steering engines can reach each other through the roads, and the distance between them is the number of edges on the shortest path between them.

There are $k$ rescue teams deployed nearby: $s_1$, $s_2$, ..., $s_k$. Each rescue team has a rescue range. A rescue range is a connected subset of the set of steering engines, where for any two engines in it, all engines on the road path between them are also within the rescue range.

We say an engine $u$ can be reached by a rescue team whose rescue range is $S$ if and only if $u$ is in $S$, and for every engine $v$ in $S$, the distance from $v$ to $u$ is no greater than $L$. In this way, no matter where the rescue team is within its post, they can reach engine $u$ before time runs out.

Cai Deren wants to command the $k$ rescue teams to gather at the same engine. But due to communication interruption, Cai Deren does not know each rescue team's rescue range. He wants to compute the number of feasible scheduling plans, so he inputs the problem into a computer.

On the other side of this computer—you need to help him count, among how many possible deployment plans there exists an engine that can be reached by all rescue teams. A plan refers to a set of rescue ranges $\left\{S_1, S_2, ..., S_k\right\}$. Two plans are different if and only if for some rescue team $s_i$, its rescue range $S_i$ is different in the two plans. In this saturating rescue jointly planned by the government, the rescue ranges of two teams may intersect or even be the same.

You know the answer is extremely large. Snow vehicles shuttle among tens of thousands of landmarks; the possible rescue ranges are vast, yet the set of all teams' plans is like a morning star. But you have no time to despair, not even time to compute that number.

You can only compute the answer modulo $998244353$.

That is hope.

Even if it needs to be taken modulo, it is still light.

Input Format

The first line contains three numbers $n$, $L$, $k$, representing the number of steering engines, the remaining time to save Earth, and the number of rescue teams.

The next $n - 1$ lines each contain two integers $u$, $v$, indicating that there is a road connecting the $u$-th and the $v$-th steering engines.

Output Format

Only one integer, representing the number of plans modulo $998244353$.

2 1 2
1 2

7

4 1 1
1 2
2 3
3 4

9

5 1 1
1 2
1 3
2 4
2 5

14

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

953325149

Hint

Sample $1$ Explanation

There are the following feasible plans:

Sample $2$ Explanation

There is only one rescue team. All plans are feasible except the one where this rescue team's rescue range is the full set $\texttt{\{1,2,3,4\}}$.

Sample $4$ Explanation

The graph for this test point is shown in the figure below:

Subtasks

For all data, $1 \leqslant n \leqslant 10^6$, $0 \leqslant L \leqslant n$, $1 \leqslant k \leqslant 10$.

Please confirm that your program uses file input/output and does not print extra debugging information.

Cai Deren looked up. It was a scene he had never seen before—Jupiter took up most of the sky, and its brilliant colors, shining through the thin atmosphere, became especially dazzling.

A small boat drifting in a boundless ocean may be overturned by a violent storm at any time; and ordinary people on the boat can only hold on to faint hope, following the heading guided by the helmsman.

He stepped forward and pressed $\texttt{Enter}$.

$ sudo ./spring12biubiu

The command has been issued.

Translated by ChatGPT 5