Little Cyan Fish ו-Little Kevinfish משחקים משחק של מיון סדרות. ל-Little Kevinfish יש עץ $T$ עם $n$ קודקודים, שבו הקודקודים ממוספרים במספרים שלמים מ-$1$ עד $n$.

עבור סדרה $A$ המורכבת ממספרים שלמים מ-$1$ עד $n$,‏ Little Kevinfish מגדיר פעולת החלפה באופן הבא:

• בחר אינדקסים $i, j$ כך שהקודקודים הממוספרים $A_i$ ו-$A_j$ מחוברים ישירות באמצעות קשת ב-$T$.
• החלף את המיקומים של $A_i$ ו-$A_j$.

Little Kevinfish שואל את Little Cyan Fish את השאלה הבאה:

• עבור קבוע נתון $m$, לכל $\ell = 1, 2, \dots, m$, פתור את הבעיה הבאה:
  • נתבונן בסדרה $A$ באורך $\ell$ המורכבת ממספרים שלמים מ-$1$ עד $n$ (ישנן $n^\ell$ סדרות כאלה בסך הכל); כמה סדרות $A$ ניתן להפוך לסדרה מונוטונית לא-יורדת באמצעות מספר כלשהו של פעולות ההחלפה הנ"ל?

אנא עזור ל-Little Cyan Fish לענות על שאלתו של Little Kevinfish. מכיוון שהתשובה עלולה להיות גדולה מאוד, עליך להדפיס את התשובה רק מודולו $10^9 + 7$.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם בודד $T$ ($1 \le T$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה של הקלט מכילה שני מספרים שלמים $n$ ו-$m$ ($1 \le n \le 200$, $1 \le m \le 10^5$).

$(n - 1)$ השורות הבאות מכילות כל אחת שני מספרים שלמים $u_i$ ו-$v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), המציינים קשת המחברת בין קודקוד $u_i$ לקודקוד $v_i$. מובטח כי $(n - 1)$ קשתות אלו יוצרות עץ תקין.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $200$, וסכום ערכי $m$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל מקרה בדיקה, הדפס שורה אחת המכילה $m$ מספרים שלמים. המספר השלם ה-$i$ ($1 \le i \le m$) מייצג את התשובה כאשר $\ell = i$, מודולו $10^9 + 7$.

דוגמאות

קלט 1

3
3 4
1 2
2 3
4 2
1 2
1 3
3 4
1 10

פלט 1

3 8 23 70
4 13
1 1 1 1 1 1 1 1 1 1