Kelian Jiutian is a girl who loves creating problems.

Today, Kelian wants to create a problem related to graph theory. On an undirected graph $G$, we can perform some very interesting transformations, such as taking the dual or the complement. Such operations often breathe new life into traditional problems. For example, finding the connectivity of a complement graph or the shortest path in a complement graph are very interesting problems.

Recently, Kelian learned about a new transformation: finding the line graph of the original graph. For an undirected graph $G = \langle V, E \rangle$, its line graph $L(G)$ is also an undirected graph: Its vertex set size is $|E|$, and each vertex corresponds uniquely to an edge in the original graph. There is an edge between two vertices if and only if the corresponding edges in the original graph share a common vertex (note that there are no self-loops).

The figure below shows a simple example. The left graph is the original graph, and the right graph is its corresponding line graph. Here, vertex 1 corresponds to edge $(1, 2)$ in the original graph, vertex 2 corresponds to $(1, 4)$, vertex 3 corresponds to $(1, 3)$, and vertex 4 corresponds to $(3, 4)$.

After some initial exploration, Kelian discovered that the properties of line graphs are much more complex than those of complement graphs. A prominent point is that the complement of a complement graph returns to the original graph, while $L(L(G))$ is not equal to $G$ in most cases, and in many cases, its number of vertices and edges grows at a very fast rate.

Therefore, Kelian wants to start with the simplest case, which is calculating the number of vertices in $L^k(G)$ (where $L^k(G)$ denotes applying the line graph transformation to $G$ for $k$ times).

Unfortunately, even this problem is too difficult for Kelian, so she simplified it. She provides a tree $T$ with $n$ nodes, and now she wants you to calculate the number of vertices in $L^k(T)$.

Input

The first line contains two integers $n$ and $k$, representing the number of nodes in the tree and the number of times the line graph transformation is applied.

The next $n - 1$ lines each contain two integers $u, v$, representing an edge in the tree.

Output

Output a single integer representing the answer modulo 998244353.

Examples

Input 1

5 3
1 2
2 3
2 5
3 4

Output 1

5

Note 1

As shown in the figure below, the left graph is the original tree, the middle graph is $L(G)$, and the right graph is $L^2(G)$. $L^3(G)$ is not drawn here, but since $L^2(G)$ has 5 edges, $L^3(G)$ has 5 vertices.

Constraints

For 100% of the data, $2 \le n \le 5000$.