题目描述

小 E 和小 F 在做游戏。他们找来了一个无向连通图 $G=(V,E)$ 。图 $G$ 满足 $V={1,2,\dots,n}$，$|E|=n$ 。

定义 $d(u,v)=G$ 中 $u$ 和 $v$ 之间的最短距离，这里 $G$ 中的每条边权值均为 $1$。小 E 会在所有满足 $u,v\in V$，且$u< v$ 的点对 $(u,v)$ 中随机选择一个，然后让小 F 求出 $d(u,v)^k$，作为这次游戏的快乐程度。

在游戏之前，小 F 想知道游戏的快乐程度的期望，于是让小 O 去算。小 O 不会算，找到了你。

输入格式

第一行包含两个整数 $n,k$ 。

接下来 $n$ 行每行两个整数 $u,v$ 表示 $(u,v)\in E$。

输出格式

设答案为 $p\over q$，且 $\gcd(p,q)=1$，则应该输出一个整数 $r$ 满足 $q\cdot r\equiv p \bmod 998244353,0\le r<998244353 $，可以证明在本题中 $r$ 是唯一的。

样例

input

4 3
1 2
2 3
3 4
2 4

output

332748121

$d(1,2)=d(2,3)=d(3,4)=d(2,4)=1$，$d(1,3)=d(1,4)=2$。

数据范围与提示

本题采用子任务制。对于所有数据满足 $1\le n\le 10^5,1\le k\le 10^9$，保证给定的图 $G$ 满足题中要求，且不存在重边。

$\texttt{subtask 1:}~ 5\%$，满足 $n\le 1000$ 。

$\texttt{subtask 2:}~10\%$，满足 $k=1$ 。

$\texttt{subtask 3:}~15\%$，满足 $k=2$ 。

$\texttt{subtask 4:}~30\%$，满足 $G$ 中存在一条边 $(u,u)$ 。

$\texttt{subtask 5:}~40\%$，无额外限制。