CF2239D Hunting the Beast

在浙江省中部的诸暨市，当地民间传说有一种名为“马头熊”的野兽。它栖息在深山之中，会在夜里潜入村庄吞食家畜，并袭击落单的旅人。尽管许多老人都声称曾亲眼见过它，但至今从未有人拍到过这种生物的照片。 一个勇敢的 $m$ 人的团队决定去山上猎杀这只野兽。这座山上的位置和小径可以被建模为一个功能图 $G$，其中有 $n$ 个点（编号为 $1$ 到 $n$）。一个功能图是一个 $n$ 个点、$n$ 条边的有向图，每个顶点的出度都恰好为 $1$。另外，我们还知道这座山的小径没有自环。 这个小组会选择刚好 $m$ 个不同的点加入它们的初始的起点集合 $S$。一个起点集合是成功的当且仅当图中的每个点 $u$ 都可以从至少一个点 $v\in S$ 到达（一个点始终可以从它自己到达）。 一共有 $\binom{n}{m}$ 中方法选择一个大小为 $m$ 的起点集合。他们定义一个图 $G$ 的分数为它所拥有的成功的起点集合的个数。 然而，这座山的确切的小径分布是未知的。如果每个点的出边的终点是从剩下的 $n-1$ 个点（除去它自己）中随机选取的，就会有 $(n-1)^n$ 个可能的功能图。给定 $n,m$，你的任务是计算所有 $(n-1)^n$ 个可能的功能图的分数之和。由于答案可能非常大，输出它对 $998\,244\,353$ 取模的值。

每个测试点拥有多组测试数据。第一行包含测试数据的个数 $t$（$1\le t\le 10^4$）。接着是每个测试数据的描述。 每个测试数据的唯一一行包含两个整数 $n,m$（$1\le m\le n\le 10^6$）——图中的总点数和起点集合的点数。 保证所有测试数据的 $n$ 之和不会超过 $10^6$。

对于每组测试数据，输出一个整数：所有 $(n-1)^n$ 个可能的功能图的分数之和，对 $998\,244\,353$ 取模。

在第一组测试数据中，有 $(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$ 个图，每个包含一个二元环和一个指向它的叶子（如，$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$。