CF2239D.Hunting the Beast

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$.

在浙江省中部的诸暨市，当地民间传说中有一种名为“魔德勇”的野兽。它栖息于深山之中，据说会在夜间潜入村庄，吞食牲畜，并袭击独行的旅人。尽管许多老人声称曾亲眼见过它，却从未有人成功拍摄到它的照片。

一支由 $m$ 人组成的勇敢队伍决定进山围猎这头野兽。整座山的地貌与路径可建模为一个具有 $n$ 个顶点（编号为 $1$ 至 $n$）的函数图（functional graph）$G$。所谓函数图，是指一个含 $n$ 个顶点和 $n$ 条有向边的有向图，其中每个顶点的出度恰好为 $1$。此外，已知山中的路径绝不会形成自环（即不存在从某顶点指向其自身的边）。

这支队伍将从中精确选择 $m$ 个互不相同的顶点，构成其初始出发集合 $S$。若图 $G$ 中任意顶点 $u$ 均可从某个 $v \in S$ 出发沿有向边路径到达（规定每个顶点自身总是可达的），则称该出发集合 $S$ 是成功的。

共有 $\binom{n}{m}$ 种方式选择大小为 $m$ 的出发集合。他们将图 $G$ 的价值定义为其中成功的出发集合的数量。

然而，山中路径的确切布局尚属未知。若对每个顶点，其唯一一条出边的终点在其余 $n-1$ 个顶点中（即排除自身）任意选取，则总共存在 $(n-1)^n$ 种可能的函数图。给定 $n$ 和 $m$，你的任务是计算所有这 $(n-1)^n$ 个可能的函数图的价值之和。由于答案可能极大，请输出其对 $998\,244\,353$ 取模的结果。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n,m$（$1\le m \le n\le 10^6$）—— 分别表示图中的顶点数和起始顶点数。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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$.

对于每个测试用例，输出一个整数——所有 $(n-1)^n$ 个可能的函数图的值之和，对 $998\,244\,353$ 取模。

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$.

在第一个测试用例中，恰好存在 $(2-1)^2=1$ 个有效的函数图：$1 \to 2$ 且 $2 \to 1$。所有大小为 $1$ 的起始集合（即 $\{1\}$ 和 $\{2\}$）均能到达全部顶点。因此，总值为 $2$。

在第二个测试用例中，共有 $(3-1)^3=8$ 个有效的函数图。它们可分类如下：

• $2$ 个图构成一个长度为 $3$ 的单环（例如 $1 \to 2 \to 3 \to 1$）。从任意一个 $3$ 个顶点出发均能到达全部顶点。这部分对总值的贡献为 $2 \cdot 3 = 6$。
• $6$ 个图由一个 $2$-环及一个指向该环的孤立叶节点组成（例如 $1 \leftrightarrow 2$ 且 $3 \to 1$）。为到达全部顶点，起始集合必须恰好为该叶节点。这部分对总值的贡献为 $6 \cdot 1 = 6$。

总值之和为 $6 + 6 = 12$。

在第三个测试用例中，可能的 $8$ 个图与前述相同，但此时我们选择大小为 $m=2$ 的子集：

• 对于 $2$ 个环图，任意大小为 $2$ 的子集均成功。这部分贡献为 $2 \cdot \binom{3}{2} = 6$。
• 对于 $6$ 个含叶节点的图，子集必须包含该叶节点。对每个图，恰有 $\binom{2}{1}=2$ 个满足条件的子集。这部分贡献为 $6 \cdot 2 = 12$。

总值之和为 $6 + 12 = 18$。