Маленькая Голубая Рыбка и Маленький Кевинфиш играют в игру с сортировкой последовательностей. У Маленького Кевинфиша есть дерево $T$ с $n$ вершинами, пронумерованными целыми числами от $1$ до $n$.

Для последовательности $A$, состоящей из целых чисел от $1$ до $n$, Маленький Кевинфиш определяет операцию обмена следующим образом: Выбрать индексы $i, j$ такие, что вершины с номерами $A_i$ и $A_j$ непосредственно соединены ребром в $T$. Поменять местами значения $A_i$ и $A_j$.

Маленький Кевинфиш задает Маленькой Голубой Рыбке следующий вопрос: Для заданной константы $m$, для каждого $\ell = 1, 2, \dots, m$, решите следующую задачу: Рассмотрим последовательность $A$ длины $\ell$, состоящую из целых чисел от $1$ до $n$ (всего существует $n^\ell$ таких последовательностей). Сколько существует последовательностей $A$, которые можно преобразовать в монотонно неубывающую последовательность с помощью некоторого количества вышеуказанных операций обмена?

Помогите Маленькой Голубой Рыбке ответить на вопрос Маленького Кевинфиша. Поскольку ответ может быть очень большим, выведите его по модулю $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