Gojo มีต้นไม้ที่มีจุดยอด $n$ จุด เขาได้เรียนรู้เทคนิคการบีบอัดอาณาเขต (domain compression) ซึ่งทำงานดังต่อไปนี้:

• ขั้นแรก เขาเลือกจุดยอด $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