D. Hunting the Beast

Source: Codeforces 2239D
Contest: Codeforces Round 1105 (Div. 1)
Time limit: 2 seconds
Memory limit: 256 megabytes

Statement

In Zhuji, a city in central Zhejiang Province, local folklore tells of a wild beast known as the Modeiyon. Dwelling deep in the mountains, it is said to sneak into villages at night to devour livestock and prey on lone travelers. Though many elders claim to have seen it, no photograph of the creature has ever been taken.

A brave group of $m$ people decides to head up the mountain to hunt the beast. The mountain's locations and trails can be modeled as a functional graph $G$ with $n$ vertices (numbered $1$ to $n$). A functional graph is a directed graph with $n$ vertices and $n$ edges, where every vertex has an out-degree of exactly $1$. Additionally, it is known that the mountain's trails do not ever form self-loops.

The group will choose exactly $m$ distinct vertices to form their initial starting set $S$. A starting set $S$ is defined as successful if every vertex $u$ in the graph is reachable from at least one vertex $v \in S$ (a vertex is always reachable from itself).

There are $\binom{n}{m}$ possible ways to choose the starting set of size $m$. They define the value of a graph $G$ as the number of successful starting sets it has.

However, the exact layout of the mountain's trails is unknown. If the destination of the single outgoing edge from each vertex is chosen arbitrarily from the remaining $n-1$ vertices (excluding the vertex itself), there are exactly $(n-1)^n$ possible functional graphs. Given $n$ and $m$, your task is to calculate the sum of the values of all $(n-1)^n$ possible functional graphs. Since the answer can be very large, print it modulo $998\,244\,353$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains two integers $n,m$ ($1\le m \le n\le 10^6$) — the number of vertices in the graph and the number of starting vertices.

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 — the sum of the values of all $(n-1)^n$ possible functional graphs, modulo $998\,244\,353$.

Note

In the first test case, there is exactly $(2-1)^2=1$ valid functional graph: $1 \to 2$ and $2 \to 1$. Both starting sets of size $1$ ($\{1\}$ and $\{2\}$) can reach all vertices. Thus, the total value is $2$.

In the second test case, there are $(3-1)^3=8$ valid functional graphs. They can be categorized as follows:

• $2$ graphs form a single cycle of length $3$ (e.g., $1 \to 2 \to 3 \to 1$). Starting at any of the $3$ vertices can reach all vertices. This contributes $2 \cdot 3 = 6$ to the total value.
• $6$ graphs consist of a $2$-cycle and a single leaf pointing to it (e.g., $1 \leftrightarrow 2$ and $3 \to 1$). To reach all vertices, the starting set must be exactly the leaf vertex. This contributes $6 \cdot 1 = 6$ to the total value.

The total sum of values is $6 + 6 = 12$. In the third test case, the $8$ possible graphs are the same, but we choose subsets of size $m=2$:

• For the $2$ cycle graphs, any subset of size $2$ is successful. This contributes $2 \cdot \binom{3}{2} = 6$.
• For the $6$ leaf graphs, the subset must contain the leaf vertex. There are exactly $\binom{2}{1}=2$ such subsets for each graph. This contributes $6 \cdot 2 = 12$.

The total sum of values is $6 + 12 = 18$.

Examples

5
2 1
3 1
3 2
4 2
8 3

2
12
18
216
20415360