19072번 - Match 다국어

Yuta has an undirected connected graph $G = \langle V, E \rangle$ with $n$ nodes and $n - 1$ edges. Yuta can choose some subset of edges in $E$ and remove them. It is clear that Yuta has $2^{n - 1}$ different subsets to remove.

Now, Yuta wants to know the number of ways to remove the edges which make the maximum matching size of the remaining graph $G'$ divisible by $m$. As the answer can be very large, find its remainder modulo $998\,244\,353$.

An edge set $S$ is a matching of $G = \langle V, E \rangle$ if and only if each node in $V$ is connected to at most one edge in $S$. The maximum matching of graph $G$ is defined as the matching of $G$ which has the largest size.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 5 \cdot 10^4$, $1 \leq m \leq 200$).

Then $n - 1$ lines follow, each of these lines contains two integers $u$ and $v$ which describe an edge in $G$.

Print a single line with a single integer: the answer modulo $998\,244\,353$.