Little Cyan Fish và Little Kevinfish đang chơi một trò chơi sắp xếp các dãy số. Little Kevinfish có một cây $T$ với $n$ đỉnh, trong đó các đỉnh được đánh số bằng các số nguyên từ $1$ đến $n$.

Đối với một dãy $A$ gồm các số nguyên từ $1$ đến $n$, Little Kevinfish định nghĩa một thao tác hoán đổi như sau:

• Chọn các chỉ số $i, j$ sao cho các đỉnh được đánh số $A_i$ và $A_j$ được nối trực tiếp bởi một cạnh trong $T$.
• Hoán đổi vị trí của $A_i$ và $A_j$.

Little Kevinfish đặt câu hỏi cho Little Cyan Fish như sau:

• Với một hằng số $m$ cho trước, với mỗi $\ell = 1, 2, \dots, m$, hãy giải bài toán sau:
  • Xét một dãy $A$ có độ dài $\ell$ gồm các số nguyên từ $1$ đến $n$ (tổng cộng có $n^\ell$ dãy như vậy), có bao nhiêu dãy $A$ có thể được biến đổi thành một dãy không giảm thông qua một số thao tác hoán đổi nêu trên.

Hãy giúp Little Cyan Fish trả lời câu hỏi của Little Kevinfish. Vì kết quả có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 200, 1 \le m \le 10^5$).

$(n - 1)$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), biểu thị một cạnh nối giữa đỉnh $u_i$ và $v_i$. Đảm bảo rằng $(n - 1)$ cạnh này tạo thành một cây hợp lệ.

Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $200$, và tổng $m$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng chứa $m$ số nguyên. Số nguyên thứ $i$ ($1 \le i \le m$) biểu thị kết quả khi $\ell = i$, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

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