Годжода $n$ төбесі бар ағаш бар. Ол аймақты сығу (domain compression) әдісін үйренді, ол келесідей жұмыс істейді:

• Алдымен ол графтан бұрын өшірілмеген қандай да бір $v$ төбесін таңдайды. Содан кейін $v$ төбесімен байланысқан әрбір $u < w$ төбелер жұбы үшін, егер $(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