$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