Background

No distance is impossible to cross.

Problem Description

Given a tree $G$, define the distance $\operatorname{dis}(u,v)$ between two nodes $u, v$ as the number of nodes on the path between them.

If for two nodes $u, v$ on the tree, the following holds: $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ and $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$, then we call the unordered pair $(u,v)$ an extremely far pair.

Also, for a node $x$ in the tree $G$, its weight $v_x$ is defined as: the number of extremely far pairs whose shortest path passes through $x$.

Given the tree $G$, compute $\sum\limits_{x \in G}{v_x^k} \bmod 998244353$, where $k$ is a given constant and $k \in [1,2]$.

Input Format

The first line contains two integers $n, k$, representing the number of nodes in the tree $G$ and the given constant.

The next $n - 1$ lines each contain two integers $u, v$, indicating that there is an edge between node $u$ and node $v$.

Output Format

Output one integer in one line, representing the answer.

2 1
1 2

2

5 2
1 2
1 3
4 1
5 1

72

Hint

Sample Explanation #1

$(1,2)$ is an extremely far pair, so the weights of nodes $1$ and $2$ are both $1$, and $1^1 + 1^1 = 2$.

Sample Explanation #2

The extremely far pairs are $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$, so the answer is $4 \times 3^2 + 6^2 = 72$.

Constraints

For $100\%$ of the testdata, $n \leq 5 \times 10^6$ and $1 \leq k \leq 2$.

The input size is large, so please use a fast input method.

Translated by ChatGPT 5