تستعد الأبقار الـ$N$ في سيرك Farmer John ($1 \leq N \leq 10^5$) لعروضها المقبلة. تجري جميع العروض على شجرة رؤوسها مرقمة من $1\ldots N$. تُعرَّف «الحالة الابتدائية» لعرض ما بعدد $1 \leq K \leq N$ وتوزيع الأبقار $1\dots K$ على رؤوس الشجرة، بحيث لا توجد بقرتان في الرأس نفسه.

خلال العرض، تنفذ الأبقار عددًا من «الحركات» يمكن أن يكون كبيرًا كيفما تشاء. في كل حركة، تنتقل بقرة واحدة من رأسها الحالي إلى رأس مجاور غير مشغول. يقال إن حالتين ابتدائيتين متكافئتان إذا أمكن الوصول إلى إحداهما من الأخرى بسلسلة من الحركات.

لكل $1 \leq K \leq N$، ساعد الأبقار على تحديد عدد فئات التكافؤ للحالات الابتدائية: أي أكبر عدد من الحالات الابتدائية يمكن اختيارها بحيث لا تكون أي حالتين منها متكافئتين. وبما أن هذه الأعداد قد تكون كبيرة جدًا، أخرج بواقي قسمتها على $10^9 + 7$.

الإدخال

يحتوي السطر $1$ على $N$.

يحتوي كل سطر من الأسطر $2\le i\le N$ على عددين صحيحين $a_i$ و$b_i$ يمثلان حافة بين $a_i$ و$b_i$ في الشجرة.

الإخراج

لكل $1\le i\le N,$، يجب أن يحتوي السطر رقم $i$ من الإخراج على إجابة $K=i$ بترديد $10^9+7$.

أمثلة

الإدخال 1

5
1 2
2 3
3 4
3 5

الإخراج 1

1
1
3
24
120

ملاحظة

عندما $K=1$ و$K=2,$، يمكن تحويل أي حالتين إحداهما إلى الأخرى.

لننظر الآن في $K=3$، ولتكن $c_i$ موقع البقرة $i$. الحالة $(c_1,c_2,c_3)=(1,2,3)$ مكافئة للحالتين $(1,2,5)$ و$(1,3,2).$ لكنها ليست مكافئة للحالة $(2,1,3).$

الإدخال 2

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

الإخراج 2

1
1
1
6
30
180
5040
40320

المهام الفرعية

• تستوفي حالات الاختبار 3–4 الشرط $N\le 8.$
• تستوفي حالات الاختبار 5–7 الشرط $N\le 16.$
• تستوفي حالات الاختبار 8–10 الشرط $N\le 100$ وتشكل الشجرة «نجمة»؛ يوجد على الأكثر رأس واحد درجته أكبر من اثنين.
• تستوفي حالات الاختبار 11–15 الشرط $N\le 100$.
• لا توجد قيود إضافية على حالات الاختبار 16–20.

صاحب المسألة: Dhruv Rohatgi