Dos tontos pasean por la calle...
Primer tonto: Eh, se me ha ocurrido un problema buenísimo. O sea, tienes un grafo dirigido acíclico, también llamado DAG... y quieres asignar a cada arista un peso de $0$ o $1$, de modo que, entre cualesquiera dos vértices, el peso del camino entre ellos no dependa del camino elegido...
Segundo tonto: Hmm... pero ¿qué pasa si no hay ningún camino entre dos vértices?
Primer tonto: Bueno, sí, cuando hay varios caminos, todos tienen el mismo peso. En fin, se pide el número de esas asignaciones de pesos.
Segundo tonto: Sí, buen problema...
Por suerte, entonces se encontraron con su amigo, que no era tonto.
Amigo que no es tonto: Seguro que vosotros no sabéis resolverlo; en otras palabras, estáis dando palos de ciego. Pero yo sé resolver un problema algo más sencillo. No puedo exigir que la distancia entre los vértices no dependa del camino elegido, pero sí puedo exigir que la distancia módulo $2$ no dependa de él...
Primer y segundo tonto: orz
Ahora, formalmente, se da un grafo dirigido con $N$ vértices y $M$ aristas. Los vértices están numerados del $1$ al $N$, y para cada arista dirigida $(u, v)$ se cumple $u < v$. Llamamos coloración de las aristas a la asignación de un valor $0$ o $1$ a cada arista. Denotamos el valor de la arista $(u, v)$ por $w(u, v)$.
Un camino entre los vértices $u$ y $v$ es cualquier secuencia de vértices $(a_1, \ldots, a_k)$ tal que $a_1 = u$ y $a_k = v$. Además, para cada $i$ entre $1$ y $k - 1$ debe existir la arista $(a_i, a_{i+1})$. El peso de un camino es la suma de los pesos de todas sus aristas, es decir, $w(a_1, a_2) + \cdots + w(a_{k-1}, a_k)$.
Una coloración $w$ es buena si, para cada par de vértices $(u, v)$ y para cada par de caminos entre ellos, los pesos de esos dos caminos tienen el mismo resto al dividirlos entre $2$.
Como el número de coloraciones buenas puede ser grande, imprime su resto al dividirlo entre $10^9 + 7$.
Entrada
La primera línea contiene los números naturales $N$ y $M$.
Las siguientes $M$ líneas contienen pares distintos de números $u$ y $v$ ($1 \le u < v \le N$), que representan las aristas del grafo.
Salida
En una única línea, imprime el resto al dividir entre $10^9 + 7$ el número de coloraciones buenas.
Subtareas
En todas las subtareas se cumple $1 \le N \le 400$, $0 \le M \le 400$.
| Subtarea | Puntos | Restricciones |
|---|---|---|
| 1 | 21 | $N \le 6$ |
| 2 | 20 | $N \le 13$ |
| 3 | 37 | $N, M \le 50$ |
| 4 | 22 | Sin restricciones adicionales. |
Ejemplos
Entrada 1
4 4 1 2 2 3 3 4 1 4
Salida 1
8
Entrada 2
4 4 1 3 1 4 2 3 2 4
Salida 2
16
Nota
Explicación del primer ejemplo:
Los caminos $1 \to 2 \to 3 \to 4$ y $1 \to 4$ deben tener el mismo peso módulo $2$. Si asignamos a la arista $(1, 4)$ un peso de $0$, un número par de las aristas restantes debe tener peso $1$, lo que da $4$ combinaciones. Si, en cambio, asignamos a la arista $(1, 4)$ un peso de $1$, un número impar de las aristas restantes debe tener peso $1$, lo que también da $4$ combinaciones.