У Ґоджо є дерево з $n$ вершинами. Він опанував техніку стиснення території, яка працює таким чином:

• Спочатку він вибирає деяку вершину $v$, яка раніше не була видалена з графа. Далі для кожної пари вершин $u < w$, з'єднаних із $v$, він додає неорієнтоване ребро $(u, w)$, якщо воно раніше не містилося в графі. Після цього він стирає $v$ з графа разом з усіма інцидентними їй ребрами.

Для кожного $k$ ($1 \le k \le n$) його цікавить загальна кількість ребер у графах, що залишилися, для всіх $\frac{n!}{(n-k)!}$ способів виконати операції. Оскільки відповіді можуть бути дуже великими, виведіть їх за модулем $998\,244\,353$.

Вхідні дані

Перший рядок містить ціле число $n$ ($2 \le n \le 10^5$) — кількість вершин у дереві.

Наступні $n - 1$ рядків містять пари цілих чисел $u_i, v_i$ ($1 \le u_i, v_i \le n$) — опис ребер дерева.

Вихідні дані

Виведіть $n$ цілих чисел — загальну кількість ребер для кожного $k$ за модулем $998\,244\,353$.

Приклади

Вхідні дані 1

5
1 2
2 3
3 5
3 4

Вихідні дані 1

16 44 60 0 0

Вхідні дані 2

8
1 2
2 3
2 4
4 5
4 7
7 8
6 7

Вихідні дані 2

51 316 1596 6120 15720 20160 0 0