ל-Gojo יש עץ עם $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