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$$$):
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$$$.
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$$$.
For each test case, output a single integer — $$$\sum_{m=1}^{k} f(m)$$$ modulo $$$998244353$$$.
23 31 22 34 71 22 31 4
8 280
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.
So the answer is $$$0 + 2 + 6 = 8$$$.