يلعب 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