D. Охота на зверя
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Чжуцзи, городе в центральной части провинции Чжэцзян, местные предания рассказывают о диком звере, известном как Модэйон. Обитая в глубине гор, он якобы прокрадывается в сёла по ночам, чтобы пожирать скот и нападать на одиноких путников. Хотя многие старейшины утверждают, что видели его, ни одной фотографии существа так и не было сделано.

Смелая группа из $$$m$$$ человек решает подняться в горы, чтобы поохотиться на зверя. Местности горы и тропы между ними можно смоделировать как функциональный граф $$$G$$$ с $$$n$$$ вершинами (пронумерованными от $$$1$$$ до $$$n$$$). Функциональный граф — это ориентированный граф с $$$n$$$ вершинами и $$$n$$$ рёбрами, в котором каждая вершина имеет исходящую степень ровно $$$1$$$. Кроме того, известно, что тропы горы не образуют петель.

Группа выберет ровно $$$m$$$ различных вершин, чтобы сформировать начальное стартовое множество $$$S$$$. Стартовое множество $$$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$$$.

Пример
Входные данные
5
2 1
3 1
3 2
4 2
8 3
Выходные данные
2
12
18
216
20415360
Примечание

В первом наборе входных данных существует ровно $$$(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$$$.