Note el límite de tiempo y memoria inusual para este problema

La Federación Interplanetaria es una alianza de ~N~ planetas, indexados de ~1~ a ~N~. Algunos planetas están conectados por túneles espaciales. En un túnel espacial, una nave puede volar en ambas direcciones muy rápido. Hay exactamente ~N-1~ túneles espaciales, y podemos viajar desde cualquier planeta a cualquier planeta en la Federación usando estos túneles.

Es bien conocido que hay ~D~ universos paralelos adicionales. Estos son copias exactas de nuestro universo, tienen los mismos planetas y túneles espaciales. Están indexados de ~1~ a ~D~ (nuestro universo tiene índice ~0~). Denotamos el planeta ~x~ en el universo ~i~ como ~P_{i, x}~. Podemos viajar de un universo a otro usando portales dimensionales para cada ~i (0 \leq i \leq D-1)~, vamos a poner exactamente un portal que nos permite volar desde ~P_{i, A_i}~ a ~P_{i+1, B_i}~, para algunos planetas ~A_i~ y ~B_i~ (i.e. ~1 \leq A_i, B_i \leq N~).

Una vez todos los portales están puestos, la nave "Selene" se embarcará en su primer viaje. Actualmente está orbitando alrededor de ~P_{0, 1}~.

La capitana Alicia y el teniente Bob han decidido jugar el siguiente juego: eligen alternadamente un destino (planeta) hacia el que volar. Este planeta puede estar en el mismo universo, si un túnel espacial va hacia allí, o puede estar en otro universo, si un portal va hacia allí. Su objetivo es visitar lugares a los que nadie haya ido antes. Por eso, una vez que visitan el planeta ~P_{i, x}~ no pueden volver (pero pueden visitar el planeta x en otro universo).

Alicia elige el primer destino. Si alguien no puede elegir un destino en su turno, pierde.

Alicia y Bob son muy inteligentes: conocen la localización de todos los túneles y portales, y ambos juegan óptimamente, Para cuántas formas distintas de poner los portales gana Alicia? Dos formas se consideran distintas si existe un índice ~i~ tal que el ~i~-ésimo portal conecta un par diferente de planetas.

Este número puede ser muy grande, nos interesa su módulo ~10^9+7~.

Subtareas

• Subtarea 1 (7 puntos): ~N = 2~.
• Subtarea 2 (8 puntos): ~N \leq 100~ y ~D = 1~.
• Subtarea 3 (15 puntos): ~N \leq 1000~ y ~D = 1~.
• Subtarea 4 (15 puntos): ~D = 1~.
• Subtarea 5 (20 puntos): ~N \leq 1000~ y ~D \leq 10^5~.
• Subtarea 6 (20 puntos): ~D \leq 10^5~.
• Subtarea 7 (15 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene 2 enteros separados por espacios, ~N~ (~2 \leq N \leq 10^5~) y ~D~ (~1 \leq D \leq 10^{18}~).

Cada una de las siguientes ~N-1~ líneas contiene 2 enteros separados por espacios ~u~ y ~v~ (~1 \leq u, v \leq N~), denotando que ~P_{i, u}~ y ~P_{i+1, v}~ están conectados por un túnel espacial.

Salida

Imprima un solo entero, el número de posibles posicionamientos de portales donde Alicia gana (módulo ~10^9+7~). Por tanto el rango de la salida es ~0, 1, 2, ..., 10^9+6~.

Ejemplo

Entrada ejemplo 1

3 1
1 2
2 3

Salida ejemplo 1

4

Nota

Solo hay un portal y ~3*3~ formas diferentes de ponerlo. Solo en 4 de estas gana el Alicia.