De nuevo AND en un árbol#13124

De nuevo AND en un árbol

5 segundos
256 megabytes

Denotemos por la cantidad de bits iguales a uno en la representación binaria de un entero no negativo .

Se te da un árbol con vértices y un entero . Para cada vértice , considera el siguiente problema.

El vértice es la raíz del árbol. A él se le asigna el número 2^m-1, mientras que a cada uno de los demás vértices se le asigna un entero de a 2^m-1, inclusive. Sea el AND bit a bit de los números que se encuentran en el camino desde la raíz hasta el vértice , incluyendo ambos extremos.

Una asignación es atractiva si \operatorname{popcount}(\operatorname{AND}(v)) es el mismo para todos los vértices distintos de la raíz. Halla la cantidad de asignaciones atractivas para cada raíz posible, módulo .

Si n=1, la única asignación se considera atractiva.

Entrada

La primera línea contiene un entero (1\le t\le10^4) — la cantidad de casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros y (1\le n,m\le10^5).

Cada una de las siguientes n-1 líneas contiene dos enteros y (1\le u,v\le n) — los extremos de una arista. Se garantiza que las aristas dadas forman un árbol.

La suma de sobre todos los casos de prueba no excede 10^5. La suma de tampoco excede 10^5.

Salida

Para cada caso de prueba, imprime una línea con enteros. El -ésimo entero debe ser la cantidad de asignaciones atractivas con raíz en el vértice , módulo .

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

En el primer caso de prueba del primer ejemplo, el árbol tiene un solo vértice, por lo que la respuesta es .

En el segundo caso de prueba del primer ejemplo, a la raíz se le asigna el número . Al otro vértice se le puede asignar cualquiera de , o , por lo que la respuesta es para cualquiera de las dos raíces.

Puntuación

  1. Subtarea ( puntos): t\le10, n,m\le5.

  2. Subtarea ( puntos): n,m\le20.

  3. Subtarea ( puntos): el grado de cada vértice es a lo sumo .

  4. Subtarea ( puntos): el árbol es una estrella, es decir, existe un vértice adyacente a todos los demás.

  5. Subtarea ( puntos): n,m\le1000, \sum n\le5000, \sum m\le5000.

  6. Subtarea ( puntos): sin restricciones adicionales.