题目背景

没有什么距离是无法跨越的。

题目描述

定义一棵树 $G$ 上两点 $u,v$ 之间的距离 $\operatorname{dis}(u,v)$ 为两点之间点的数量。

若对于树上两点 $u,v$，满足 $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ 且 $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$，那么我们称无序点对 $(u,v)$ 为极远点对。

同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。

现给定树 $G$，求 $\sum\limits_{x \in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \in [1,2]$。

输入格式

第一行两个数 $n,k$，分别表示树 $G$ 的点数以及给定的常数。

接下来 $n-1$ 行每行两个整数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。

输出格式

输出一行一个整数，表示答案。

2 1
1 2

2

5 2
1 2
1 3
4 1
5 1

72

提示

样例解释 #1

$(1,2)$ 为极远点对，所以 $1$ 号和 $2$ 号点点权均为 $1$，$1^1 + 1^1 =2$。

样例解释 #2

极远点对有 $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$，故答案为 $4 \times 3^2 + 6^2 = 72$。

数据范围

对于 $100\%$ 的数据，满足 $n \leq 5 \times 10^6$，$1 \leq k \leq 2$。

本题输入量较大，请用较快的输入方法。