405666: GYM102028 G Shortest Paths on Random Forests

Here is a problem related to forest, which is a special type of graph. Before introducing this problem to you, we intend to show some definitions used in this problem. A labelled forest with $$$n$$$ vertices is an acyclic undirected simple graph in which vertices are labelled by $$$1, 2, \cdots, n$$$. Two labelled forests are regarded as different if their numbers of vertices are different or, if they have the same number of vertices, for some integers $$$i$$$ and for vertices labelled by $$$i$$$ in these two forests, their neighbours have different labels (which means that the sets of labels corresponding to all neighbours of vertices labelled by $$$i$$$ in these two forests are different).

Tree-like structures are constructed in computer programming constantly, which is the most fascinating part Bob has ever seen. Today, Bob wants to randomly choose a labelled forest $$$G$$$ from all possible labelled forests having $$$n$$$ vertices with equal probability. Then, he will set $$$\delta(i, j)$$$ to the number of edges on the shortest path from the vertex labelled $$$i$$$ to the vertex labelled $$$j$$$ if the shortest path exists, or set $$$\delta(i, j)$$$ to $$$m$$$ otherwise. Bob is curious about the expected value of

$$$$$$\sum_{i = 1}^{n}{\sum_{j = i + 1}^{n}{\delta^2(i, j)}},$$$$$$

but it's hard for him. Can you help Bob find out the expected value modulo $$$998244353$$$?

More precisely, if the reduced fraction of the expected value is $$$\frac{p}{q}$$$, what you should provide is the minimum non-negative integer $$$r$$$ such that $$$q r \equiv p \pmod{998244353}$$$.

The input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$2 \times 10^5$$$.

For each test case, the only one line contains two integers $$$n$$$ and $$$m$$$ where $$$1 \leq n \leq 2 \times 10^5$$$ and $$$n \leq m \leq 998244352$$$.

We guarantee that the modular multiplicative inverse of $$$q$$$ in each test case always exists, in other words, the condition $$$q \not \equiv 0 \pmod{998244353}$$$ is guaranteed to be true in all test cases.

For each test case, output a line containing the answer modulo $$$998244353$$$.

4
1 1
2 3
3 7
4 16

0
5
66
576