E. Counting Is Fun
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes and a positive integer $$$c$$$. The $$$i$$$-th edge connects the nodes $$$u_i$$$ and $$$v_i$$$.

Before the traversal begins, choose a permutation $$$p$$$ of $$$[1, 2, \ldots, n - 1]$$$ and label the $$$i$$$-th edge with $$$p_i$$$. These labels remain fixed throughout the traversal.

You start from node $$$1$$$ with an integer $$$x = 1$$$.

During the traversal, you may repeatedly perform one of the following operations:

  • Operation A: Traverse an edge adjacent to your current node if it is not labelled with $$$x$$$. After traversing, you move to the node on the other end of that edge.
  • Operation B: Increment $$$x$$$ by $$$1$$$.

You must start at node $$$1$$$, visit all nodes, and return to node $$$1$$$. The cost of a traversal is the number of times you perform Operation B.

Define $$$f(p)$$$ as the minimum cost of a traversal when the edges are labelled according to the permutation $$$p$$$.

Your task is to count the number of permutations $$$p$$$ of $$$[1, 2, \ldots n - 1]$$$ such that $$$f(p) = c$$$. Since the number might be large, output it modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains integers $$$n$$$ and $$$c$$$ ($$$2 \le n \leq 2 \cdot 10^5$$$, $$$1 \le c \le n - 1$$$) — the number of vertices and the target cost.

The next $$$n-1$$$ lines describe the edges of the tree. The $$$i$$$-th of these lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$) — the endpoints of the $$$i$$$-th edge.

The edges are numbered in the order they are given in the input. You will later label the $$$i$$$-th edge with $$$p_i$$$, where $$$p$$$ is a permutation of $$$[1, 2, \ldots, n - 1]$$$.

It is guaranteed that the given edges form a tree, and that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test, find the number of valid permutations modulo $$$998\,244\,353$$$.

Example
Input
3
2 1
1 2
5 1
1 2
1 3
1 4
1 5
5 3
1 2
1 3
1 4
1 5
Output
1
24
0
Note

In the second test case, all $$$(n-1)!$$$ permutations are valid.

In the third test case, it can be proven that no permutation is valid.