Permítanme ser directo: las cosas no van bien. Lo que se suponía que sería una tarde relajante con amigos ha dado un giro para peor: fuiste atacado por un anuncio viviente de colonia barata, y tu invaluable cactus argentino —lo único que aprecias— fue arrojado por la ventana.

Justo después del acto —o, debería decir, tan pronto como fue físicamente posible— bajaste las escaleras corriendo para evaluar las pérdidas. Y ahí estaba, tu invaluable cactus, ¡vivo! Con algunos rasguños aquí y allá, pero vivo al fin y al cabo. ¿Cómo sucedió esto? ¿Acaso aterrizó en algo blando? Abrumado por la alegría, decides no buscar respuestas. ¿Dije que las cosas no iban bien? Olvídalo, todo es genial, ¡y es hora de celebrar! Por supuesto, en el corazón de esta celebración estará tu verde y espinoso amigo.

Aquellos menos familiarizados con la botánica pueden apreciar un repaso: un cactus es un grafo conexo donde cada vértice pertenece a, como máximo, un ciclo. Para añadir al ambiente festivo, decides colorear cada vértice de tu cactus con uno de $k$ colores. Te gustaría tener mucha libertad aquí, pero quieres cumplir con la regla de oro de la coloración de cactus: no se deben asignar el mismo color a dos vértices adyacentes.

Una coloración no parece suficiente, así que decides que, después de que los colores se desvanezcan, volverás a colorear el cactus una y otra vez, usando una coloración diferente cada vez. Pero, ¿cuánto tiempo podrás seguir haciendo esto? Dada la descripción de tu cactus y el número $k$, cuenta el número de coloraciones correctas de los vértices del cactus. Dado que la respuesta puede ser muy grande, basta con calcular su resto módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 50\,000$). A continuación siguen las descripciones de los casos de prueba.

La primera línea de un caso de prueba contiene tres enteros $n$, $m$ y $k$ ($1 \le n \le 300\,000$, $0 \le m \le 400\,000$, $2 \le k \le 10^9$) — el número de vértices y aristas de tu cactus, y el número de colores.

Las siguientes $m$ líneas contienen dos enteros $u_i$, $v_i$ ($1 \le u_i \neq v_i \le n$) cada una, correspondientes a las aristas del cactus. Se garantiza que el grafo dado es un cactus y que cada dos vértices están conectados por, como máximo, una arista.

El número total de vértices y aristas en todos los casos de prueba no supera $3 \cdot 10^6$ y $4 \cdot 10^6$, respectivamente.

Salida

Para cada caso de prueba, imprime un solo entero: el número de coloraciones propias de los vértices del cactus con $k$ colores, tomado módulo $10^9 + 7$.

Ejemplos

Entrada 1

2
2 1 100
1 2
6 7 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4

Salida 1

9900
24