Deux idiots se promènent dans la rue…

Premier idiot : Hé, j'ai trouvé un super problème. Tu vois, tu as un graphe orienté acyclique, autrement dit un DAG… et tu veux attribuer à chaque arc un poids de $0$ ou $1$, de sorte qu'entre deux sommets quelconques, le poids d'un chemin ne dépende pas du chemin choisi…

Deuxième idiot : Hmm… mais s'il n'existe aucun chemin entre certains sommets ?

Premier idiot : Oui, bon, lorsqu'il existe plusieurs chemins, ils ont tous le même poids. Bref, on cherche le nombre de telles attributions de poids.

Deuxième idiot : Oui, c'est un bon problème…

Heureusement, ils rencontrent alors leur ami, qui n'est pas un idiot.

L'ami : Vous ne savez certainement pas résoudre ça ; autrement dit, vous picorez. Mais moi, je sais résoudre un problème un peu plus simple. Je ne peux pas exiger que la distance entre les sommets ne dépende pas du chemin choisi, mais je peux exiger que la distance modulo $2$ n'en dépende pas…

Les deux idiots : orz

Passons maintenant à la définition formelle. On vous donne un graphe orienté à $N$ sommets et $M$ arcs. Les sommets sont numérotés de $1$ à $N$, et chaque arc orienté $(u,v)$ vérifie $u<v$. Une coloration des arcs consiste à attribuer à chaque arc une valeur de $0$ ou $1$. La valeur de l'arc $(u,v)$ est notée $w(u,v)$.

Un chemin entre les sommets $u$ et $v$ est une suite de sommets $(a_1,\ldots,a_k)$ telle que $a_1=u$ et $a_k=v$. De plus, pour tout $i$ entre $1$ et $k-1$, l'arc $(a_i,a_{i+1})$ doit exister. Le poids du chemin est la somme des poids de tous ses arcs, c'est-à-dire $w(a_1,a_2)+\ldots+w(a_{k-1},a_k)$.

Une coloration $w$ est bonne si, pour toute paire de sommets $(u,v)$ et pour toute paire de chemins entre eux, les poids de ces deux chemins ont le même reste dans la division par $2$.

Comme le nombre de bonnes colorations peut être grand, affichez son reste dans la division par $10^9+7$.

Entrée

La première ligne contient les entiers naturels $N$ et $M$.

Les $M$ lignes suivantes contiennent des paires distinctes de nombres $u$ et $v$ ($1\le u<v\le N$), qui représentent les arcs du graphe.

Sortie

Sur une seule ligne, affichez le reste dans la division par $10^9+7$ du nombre de bonnes colorations.

Sous-tâches

Dans toutes les sous-tâches, $1\le N\le 400$ et $0\le M\le 400$.

Exemples

Entrée 1

4 4
1 2
2 3
3 4
1 4

Sortie 1

8

Entrée 2

4 4
1 3
1 4
2 3
2 4

Sortie 2

16

Remarque

Explication du premier exemple :

Les chemins $1\to 2\to 3\to 4$ et $1\to 4$ doivent avoir le même poids modulo $2$. Si nous attribuons à l'arc $(1,4)$ le poids $0$, un nombre pair des arcs restants doit avoir le poids $1$, ce qui donne $4$ combinaisons. Si, en revanche, nous attribuons à l'arc $(1,4)$ le poids $1$, un nombre impair des arcs restants doit avoir le poids $1$, ce qui donne à nouveau $4$ combinaisons.