二人の間抜けが通りを歩いている……

一人目の間抜け：「すごくいい問題を思いついたんだ。有向非巡回グラフ、つまり DAG があって……各辺に重み $0$ か $1$ を割り当てるんだ。どの二つの頂点についても、それらを結ぶパスの重みが、どのパスを選ぶかによらないようにね……」

二人目の間抜け：「うーん……でも、ある二つの頂点の間にパスがなかったら？」

一人目の間抜け：「ああ、そうだね。パスが複数あるとき、それらの重みが全部同じになるんだ。とにかく、そういう重みの割り当て方の数を求める問題だよ。」

二人目の間抜け：「うん、いい問題だね……」

幸運にも、そのとき二人は間抜けではない友人に出会った。

間抜けではない友人：「君たちにはきっと解けないよ。つまり、つついているだけだね。でも僕なら、もう少し簡単な問題は解ける。頂点間の距離がパスの選び方によらないとは要求できないけれど、距離を $2$ で割った余りがよらない、という条件なら要求できるんだ……」

一人目と二人目の間抜け：「orz」

ここからは形式的に説明する。頂点数 $N$、辺数 $M$ の有向グラフが与えられる。頂点には $1$ から $N$ までの番号が付けられ、すべての有向辺 $(u,v)$ について $u < v$ が成り立つ。各辺に値 $0$ または $1$ を割り当てることを辺の彩色と呼ぶ。辺 $(u,v)$ の値を $w(u,v)$ と表す。

頂点 $u$ から頂点 $v$ へのパスとは、$a_1 = u$、$a_k = v$ を満たす頂点列 $(a_1,\ldots,a_k)$ のことである。また、$1$ から $k-1$ までのすべての $i$ について、辺 $(a_i,a_{i+1})$ が存在しなければならない。パスの重みは、その上にあるすべての辺の重みの和、つまり $w(a_1,a_2)+\ldots+w(a_{k-1},a_k)$ である。

彩色 $w$ がよい彩色であるとは、すべての頂点対 $(u,v)$ と、それらを結ぶ任意の二つのパスについて、二つのパスの重みを $2$ で割った余りが等しいことである。

よい彩色の数は大きくなることがあるので、その数を $10^9+7$ で割った余りを出力せよ。

入力

最初の行に自然数 $N$、$M$ が与えられる。

続く $M$ 行には、グラフの辺を表す互いに異なる数の組 $u$、$v$ ($1 \le u < v \le N$) が与えられる。

出力

よい彩色の数を $10^9+7$ で割った余りを一行に出力せよ。

小課題

すべての小課題で $1 \le N \le 400$、$0 \le M \le 400$ が成り立つ。

入出力例

入力 1

4 4
1 2
2 3
3 4
1 4

出力 1

8

入力 2

4 4
1 3
1 4
2 3
2 4

出力 2

16

注記

最初の入出力例の説明：

パス $1 \to 2 \to 3 \to 4$ と $1 \to 4$ の重みを $2$ で割った余りは等しくなければならない。辺 $(1,4)$ に重み $0$ を割り当てる場合、残りの辺のうち重み $1$ の辺の数が偶数でなければならず、4 通りの組み合わせがある。一方、辺 $(1,4)$ に重み $1$ を割り当てる場合、残りの辺のうち重み $1$ の辺の数が奇数でなければならず、この場合も 4 通りの組み合わせがある。