K. The Great Withering
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes.

Consider assigning an integer weight from $$$1$$$ to $$$m$$$ to each of the $$$n-1$$$ edges. Different edges may have the same weight.

You will remove all $$$n$$$ nodes one by one. At step $$$i$$$ ($$$1 \leq i \leq n$$$):

  • Pick any remaining node $$$u$$$. Let $$$s_i$$$ be the sum of weights of all edges currently connected to $$$u$$$ ($$$s_i = 0$$$ if no edges are connected).
  • Remove $$$u$$$ along with all edges currently connected to it.

A weight assignment is valid if there exists a removal order such that $$$s_1 \gt s_2 \gt \cdots \gt s_n$$$. Let $$$f(m)$$$ denote the number of valid assignments among all $$$m^{n-1}$$$ possible ways of assigning weights from $$$1$$$ to $$$m$$$.

Given an integer $$$k$$$, compute $$$\sum_{m=1}^{k} f(m)$$$ modulo $$$998244353$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^6$$$, $$$1 \leq k \leq 10^9$$$).

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) indicating there is an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer — $$$\sum_{m=1}^{k} f(m)$$$ modulo $$$998244353$$$.

Example
Input
2
3 3
1 2
2 3
4 7
1 2
2 3
1 4
Output
8
280
Note

In the first test case, the tree is a path: $$$1 - 2 - 3$$$. Let $$$[w_1, w_2]$$$ denote the weights of edges $$$(1,2)$$$ and $$$(2,3)$$$ respectively.

  • $$$f(1) = 0$$$: No valid assignments.
  • $$$f(2) = 2$$$: Valid assignments are $$$[1, 2]$$$ and $$$[2, 1]$$$.
  • $$$f(3) = 6$$$: Valid assignments are $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$, and $$$[3, 2]$$$.

So the answer is $$$0 + 2 + 6 = 8$$$.