Рассмотрим следующую задачу:
Дано дерево с $$$n$$$ вершинами, корень которого находится в вершине $$$1$$$. Для каждой вершины $$$1 \leq i \leq n$$$ в момент времени $$$l_i$$$ на корень заедет автомобиль. Затем он мгновенно проследует из корня в вершину $$$i$$$ по единственному простому пути и припаркуется там. Он покинет вершину по тому же пути в обратную сторону в момент времени $$$r_i$$$.
Пока автомобиль припаркован на вершине, он блокирует другие автомобили от проезда через эту вершину. Дерево называется корректным, если и только если все автомобили могут заехать и выехать из дерева в желаемое время.
Посчитайте количество пар последовательностей $$$l$$$, $$$r$$$ таких, что $$$l_i \lt r_i$$$, их конкатенация является перестановкой $$$1 \ldots 2n$$$, и дерево является корректным.
Вычислите сумму ответов на задачу для всех нумерованных деревьев$$$^{\text{∗}}$$$ с $$$n$$$ вершинами и $$$k$$$ листьями. Корень не считается листом. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
$$$^{\text{∗}}$$$Два нумерованных дерева считаются различными, если и только если их множества рёбер различны.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq k \lt n \leq 2 \cdot 10^5$$$) — количество вершин и листьев дерева соответственно.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — ответ по модулю $$$998\,244\,353$$$.
32 18 365 43
3 899171636 38330886
В первом случае существует только одно дерево, которое удовлетворяет ограничениям. Корректные пары последовательностей: $$$$$$ (l, r) = \bigl([1, 3], [2, 4]\bigr),\:\bigl([3, 1], [4, 2]\bigr),\:\bigl([2, 1], [3, 4]\bigr). $$$$$$
