Descripción

Dado un arbol no dirigido con ~N~ vertices.

Taea

Encuentra cuantas formas hay de orientar las aristas del arbol tal que el grafo resultante contiene exactamente ~M~ vertices que sean vertederos. Un vertice se dice vertedero si no sale ninguna arista de el.

Entrada

La primera linea tendra la cantidad de casos ~T(1\leq T\leq 3)~ a resolver. Cada caso iniciara con una linea con dos enteros ~N~ y ~M(1\leq N\leq 1000, 0\leq M\leq N)~. Luego en las siguientes ~N-1~ lineas siguientes se tendran enteros ~u~ y ~v~~(1\leq u,v\leq N)~ especificando las aristas del arbol.

Salida

Una linea por cada caso con la cantidad de formas de orientar el arbol y haya ~M~ vertices vertedero. Como esta cantidad puede ser muy grande debes imprimirla modulo ~10^9+7~.

Ejemplo Entrada

3
1 0
1 1
5 2
1 2
2 3
3 4
3 5

Salida

0
1
8

Subtareas

1 - ~N\leq 20~, vale 15pts

2 - ~v_i = u_i + 1~, el arbol forma una linea recta a lo largo ~(N\leq 1000)~, vale 25pts

3 - ~(N\leq 200)~, vale 30pts

4 - Sin restricciones, vale 30pts