Little E and Little F are playing a game. They have an undirected connected graph $G=(V,E)$. The graph $G$ satisfies $V=\{1,2,\dots,n\}$ and $|E|=n$.

Define $d(u,v)$ as the shortest distance between $u$ and $v$ in $G$, where each edge in $G$ has a weight of $1$. Little E will randomly select a pair of vertices $(u,v)$ from all pairs satisfying $u,v\in V$ and $u

Before the game, Little F wants to know the expected value of the happiness level, so he asks Little O to calculate it. Little O cannot calculate it, so he comes to you.

Input

The first line contains two integers $n, k$.

The next $n$ lines each contain two integers $u, v$, representing an edge $(u,v)\in E$.

Output

Let the answer be $\frac{p}{q}$, where $\gcd(p,q)=1$. You should output an integer $r$ such that $q\cdot r\equiv p \pmod{998244353}$ and $0\le r< 998244353$. It can be proven that $r$ is unique in this problem.

Examples

Input 1

4 3
1 2
2 3
3 4
2 4

Output 1

332748121

Note

$d(1,2)=d(2,3)=d(3,4)=d(2,4)=1$, $d(1,3)=d(1,4)=2$.

Subtasks

This problem uses a subtask system. For all data, $1\le n\le 10^5$ and $1\le k\le 10^9$. It is guaranteed that the given graph $G$ satisfies the requirements and contains no multiple edges.

• Subtask 1: $5\%$, $n\le 1000$.
• Subtask 2: $10\%$, $k=1$.
• Subtask 3: $15\%$, $k=2$.
• Subtask 4: $30\%$, $G$ contains an edge $(u,u)$.
• Subtask 5: $40\%$, no additional restrictions.