Bessie e as vacas vizinhas decidiram ligar suas fazendas com trilhas para criar uma aliança contra os fazendeiros. Cada uma das $N$ fazendas ($1 \le N \le 100,000$) deveria construir uma trilha para exatamente outra, totalizando $N$. Após meses, só $M$ foram construídas ($1 \le M < N$).

Discussões sobre quem já construiu ameaçam dividir a aliança. Bessie quer contar as formas de construir as $M$ trilhas existentes para aliviar tensões. Uma entre 3 e 4 pode ter sido construída pela fazenda 3 ou 4. Conte as atribuições das trilhas às fazendas construtoras módulo 1,000,000,007. Duas diferem se ao menos uma trilha tem construtora diferente.

Entrada

• Linha 1: os inteiros $N$ e $M$ separados por espaço.
• Linhas $2..1+M$: a linha $i+1$ descreve a trilha $i$ com $u_{i}$ e $v_{i}$ separados por espaço ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), as fazendas ligadas.

Saída

• Linha 1: o número de atribuições módulo 1,000,000,007. Se nenhuma satisfizer as condições, imprima 0.

Exemplos

Entrada 1

5 4
1 2
3 2
4 5
4 5

Saída 1

6

Explicação

Pode haver duas trilhas entre o mesmo par de fazendas.

Há 6 atribuições. $\{a,b,c,d\}$ significa que a fazenda 1 constrói a trilha a, a 2 a b, a 3 a c e a 4 a d. As atribuições são: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Autor: Mark Gordon, 2011