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