Zwei Dummköpfe gehen die Straße entlang ...

Erster Dummkopf: Hey, ich habe mir eine richtig tolle Aufgabe ausgedacht. Also, du hast einen gerichteten azyklischen Graphen, auch DAG genannt ... und möchtest jeder Kante das Gewicht $0$ oder $1$ zuweisen, sodass das Gewicht eines Pfades zwischen je zwei Knoten nicht von der Wahl des Pfades abhängt ...

Zweiter Dummkopf: Hmm ... aber was ist, wenn es zwischen zwei Knoten keinen Pfad gibt?

Erster Dummkopf: Na gut, ja, wenn es mehrere Pfade gibt, haben sie alle dasselbe Gewicht. Jedenfalls ist die Anzahl solcher Gewichtszuteilungen gesucht.

Zweiter Dummkopf: Ja, eine gute Aufgabe ...

Zum Glück trafen sie dann ihren Freund, der kein Dummkopf ist.

Nichtdummkopf: Ihr könnt das bestimmt nicht lösen, mit anderen Worten, ihr stochert im Dunkeln. Aber ich kann eine etwas einfachere Aufgabe lösen. Ich kann zwar nicht verlangen, dass der Abstand zwischen Knoten nicht von der Wahl des Pfades abhängt, aber ich kann verlangen, dass der Abstand modulo $2$ nicht davon abhängt ...

Erster und zweiter Dummkopf: orz

Nun formal: Gegeben ist ein gerichteter Graph mit $N$ Knoten und $M$ Kanten. Die Knoten sind mit den Zahlen von $1$ bis $N$ beschriftet, und für jede gerichtete Kante $(u,v)$ gilt $u < v$. Unter einer Kantenfärbung verstehen wir die Zuweisung des Wertes $0$ oder $1$ an jede Kante. Den Wert der Kante $(u,v)$ bezeichnen wir mit $w(u,v)$.

Ein Pfad zwischen den Knoten $u$ und $v$ ist eine beliebige Knotenfolge $(a_1,\ldots,a_k)$ mit $a_1=u$ und $a_k=v$. Außerdem muss für jedes $i$ zwischen $1$ und $k-1$ eine Kante $(a_i,a_{i+1})$ existieren. Das Gewicht eines Pfades ist die Summe der Gewichte aller seiner Kanten, also $w(a_1,a_2)+\ldots+w(a_{k-1},a_k)$.

Eine Färbung $w$ ist gut, wenn für jedes Knotenpaar $(u,v)$ und jedes Paar von Pfaden zwischen diesen Knoten die Gewichte beider Pfade denselben Rest bei der Division durch $2$ haben.

Da die Anzahl guter Färbungen groß sein kann, gib ihren Rest bei der Division durch $10^9+7$ aus.

Eingabe

Die erste Zeile enthält die natürlichen Zahlen $N$ und $M$.

Die nächsten $M$ Zeilen enthalten verschiedene Zahlenpaare $u$ und $v$ ($1 \le u < v \le N$), welche die Kanten des Graphen angeben.

Ausgabe

Gib in der einzigen Zeile den Rest der Anzahl guter Färbungen bei der Division durch $10^9+7$ aus.

Teilaufgaben

In allen Teilaufgaben gilt $1 \le N \le 400$ und $0 \le M \le 400$.

Beispiele

Eingabe 1

4 4
1 2
2 3
3 4
1 4

Ausgabe 1

8

Hinweis

Erklärung zum ersten Beispiel: Die Pfade $1\to2\to3\to4$ und $1\to4$ müssen modulo $2$ dasselbe Gewicht haben. Wenn wir der Kante $(1,4)$ das Gewicht $0$ zuweisen, muss eine gerade Anzahl der übrigen Kanten das Gewicht $1$ haben. Das ergibt $4$ Kombinationen. Wenn wir hingegen der Kante $(1,4)$ das Gewicht $1$ zuweisen, muss eine ungerade Anzahl der übrigen Kanten das Gewicht $1$ haben. Das ergibt ebenfalls $4$ Kombinationen.

Eingabe 2

4 4
1 3
1 4
2 3
2 4

Ausgabe 2

16