Se te proporciona un grafo no dirigido con ~n~ nodos y ~m~ aristas.

Consideramos subgrafos que contienen todos los nodos del grafo original y algunas de sus aristas. Un subgrafo se denomina euleriano si cada nodo tiene grado par.

Tu tarea es contar el número de subgrafos eulerianos módulo ~10^9+7~.

Entrada

La primera línea de entrada contiene dos enteros, ~n~ y ~m~: el número de nodos y aristas. Los nodos están numerados del ~1~ al ~n~.

A continuación, hay ~m~ líneas que describen las aristas. Cada línea contiene dos enteros, ~a~ y ~b~: existe una arista entre los nodos ~a~ y ~b~. Hay como máximo una arista entre dos nodos, y cada arista conecta dos nodos distintos.

Salida

Imprime el número de subgrafos eulerianos módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 10^5~
• ~0 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

4 3
1 2
1 3
2 3

Ejemplo de Salida

2

Explicación: Se pueden conservar o eliminar todas las aristas, por lo que existen dos subgrafos eulerianos posibles.