Nauuo — девочка, которая любит рисовать окружности.
Однажды она нарисовала окружность и захотела нарисовать на ней дерево.
Дерево — это связный неориентированный граф из \(n\) вершин и \(n-1\) ребер. Вершины пронумерованы целыми числами от \(1\) до \(n\).
Nauuo хочет нарисовать дерево на окружности, причем вершины должны лежать на \(n\) различных точках на окружности, а ребра — это отрезки, не пересекающиеся друг с другом.
«Не пересекающиеся друг с другом» означает, что любые два ребра не должны иметь общих точек, кроме концов отрезков.
Nauuo хочет нарисовать дерево, используя перестановку из \(n\) элементов. Перестановка из \(n\) элементов это последовательность целых чисел \(p_1,p_2,\ldots,p_n\), в которой каждое целое число от \(1\) до \(n\) встречается ровно один раз.
После выбора перестановки Nauuo нарисует \(i\)-ю вершину в \(p_i\)-й точке на окружности, а затем нарисует ребра, основываясь на положении вершин.
По данному дереву Nauuo хочет знать, сколько есть перестановок, подходящих под условие (ребра образуют непересекающиеся отрезки между вершинами). Она хочет узнать ответ по модулю \(998244353\), можете ли вы ей помочь?
Очевидно, что корректность перестановки не зависит от выбранных \(n\) точек на окружности.
Выходные данные
Выведите одно целое число — количество перестановок, при которых возможно нарисовать дерево на окружности, не нарушая условия, по модулю \(998244353\).
Примечание
Пример 1
Корректные перестановки и их деревья.
А вот пример некорректной перестановки: ребра \((1,3)\) и \((2,4)\) пересекаются.
Example 2
Каждая перестановка приводит к корректному дереву, так что ответ равен \(4! = 24\).