Рассмотрим все деревья (связные неориентированные ациклические графы) на \(n\) вершинах (\(n\) нечетное, вершины пронумерованы от \(1\) до \(n\)) такие, что для каждого \(2 \le i \le n\) \(i\)-я вершина смежна ровно одной вершине с меньшим номером.
Для каждого \(i\) (\(1 \le i \le n\)) найдите количество деревьев, для которых \(i\)-я вершина является центроидом. Ответ может быть очень большим, поэтому выведите его по модулю \(998\,244\,353\).
Центроидом называется вершина, после удаления которой дерево разбивается на поддеревья, каждое из которых состоит из не более чем \((n-1)/2\) вершин.
Выходные данные
В одну строку выведите \(n\) целых чисел, \(i\)-е из которых должно быть равно ответу для \(i\)-й вершины (по модулю \(998\,244\,353\)).
Примечание
Пример \(1\): существует два возможных дерева: с ребрами \((1-2)\), и \((1-3)\) — здесь центроидом является вершина \(1\); и с ребрами \((1-2)\), и \((2-3)\) — здесь центроидом является вершина \(2\). Таким образом, ответ равен \(1, 1, 0\).
Пример \(2\): существует \(24\) возможных дерева. Например, подойдет дерево с ребрами \((1-2)\), \((2-3)\), \((3-4)\), и \((4-5)\). Здесь центроидом является вершина \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
1 1 0
|
|
2
|
5
|
10 10 4 0 0
|
|
3
|
7
|
276 276 132 36 0 0 0
|