配点 : $1600$ 点

問題文

$N$ 頂点 $M$ 辺の有向グラフ $G$ があります。 頂点には $1$ から $N$ まで番号が振られています。 辺には $1$ から $M$ まで番号が振られています。 辺 $i$ は頂点 $x_i$ から $y_i$ へ張られています。 ただし、$x_i < y_i$ です。 また、多重辺はありません。

$G$ の $M$ 本の辺集合からある部分集合を選び、$G$ からそれらの辺を取り除いてグラフ $G'$ を作ることを考えます。 このとき、グラフ $G'$ は $2^M$ 通りあり得ます。

グラフ $G'$ の上で、高橋君と青木君が次のようなゲームで勝負します。 まず、頂点 $1$, $2$ に駒をひとつずつ置きます。 高橋君から始め、高橋君と青木君が交互に次の操作を行います。

• 頂点 $x_i$ に駒が置かれているような辺 $i$ を選び、頂点 $x_i$ の駒 ($2$ つある場合は一方のみ) を頂点 $y_i$ へ移動する。 $2$ つの駒が同一の頂点に置かれてもよい。

先に操作を行えなくなった方が負けです。 二人は最適に行動するとします。

$2^M$ 通りの $G'$ のうち、高橋君が勝つような $G'$ は何通りでしょうか？ $10^9+7$ で割った余りを求めてください。

制約

• $2 \leq N \leq 15$
• $1 \leq M \leq N(N-1)/2$
• $1 \leq x_i < y_i \leq N$
• $(x_i,\ y_i)$ はすべて相異なる。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_M$ $y_M$

出力

高橋君が勝つような $G'$ は何通りか？ $10^9+7$ で割った余りを出力せよ。

2 1
1 2

1

$G'$ は次図の $2$ 通りです。 高橋君が勝つ場合は ○ で、負ける場合は × で表しています。

3 3
1 2
1 3
2 3

6

$G'$ は次図の $8$ 通りです。

4 2
1 3
2 4

2

5 10
2 4
3 4
2 5
2 3
1 2
3 5
1 3
1 5
4 5
1 4

816