Problem Statement

T.T. likes trees, and he is going to play by painting each edge of a tree with a color. However, T.T. also likes majority votes, so he wants to paint the edges so that all of the following conditions are satisfied.

• Each edge is painted with exactly $1$ color.
• Each color is painted on at least $1$ edge.
• For each vertex, if there exists a color painted on a majority (strictly more than half) of the edges incident to that vertex, then all edges incident to that vertex are painted with the same color.

Given a tree with $N$ vertices and the number of colors $C$ to use, find the number of such ways to paint the edges. Here, the colors are distinguishable from one another, and $2$ ways of painting are considered different if there exists an edge painted with different colors in them. Since the answer can be very large, output it modulo the prime $998244353$.

Input

$N$ $C$
$A_1\ \ B_1$
$A_2\ \ B_2$
   $\vdots$
$A_{N-1}\ \ B_{N-1}$

• $2 \le N \le 10^5$
• $1 \le C \le 256$
• $1 \le A_i, B_i \le N \ \ (1 \le i \le N - 1)$
• All input values are integers.
• The given graph is a tree.
• The vertices are numbered $1, 2, \dots, N$.
• The edges are numbered $1, 2, \dots, N - 1$.
• Edge $i$ connects vertex $A_i$ and vertex $B_i$.

Output

Output the total number of ways to paint the edges satisfying the conditions, modulo $998244353$.

Sample

5 2
1 2
1 3
1 4
1 5

6

5 2
1 2
3 2
3 4
5 4

14

7 4
1 2
1 3
1 4
2 5
2 6
2 7

816

7 256
1 2
1 3
1 4
2 5
2 6
2 7

0