시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

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$.

예제 입력 1

4 2
1 2
2 3
3 4

예제 출력 1

3