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