题目描述

$N$ 頂点 $M$ 辺の有向グラフ $G$ があります。 頂点には $1$ から $N$ まで番号が振られています。 辺には $1$ から $M$ まで番号が振られています。 辺 $i$ は頂点 $x_i$ から $y_i$ へ張られています。 ただし、$x_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$ で割った余りを求めてください。

输入格式

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

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出格式

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

题目大意

给定一个$n$个点$m$条边的DAG，对于每条边$(u,v)$都满足$u<v$，$1,2$号点各一个石头，每次可以沿DAG上的边移动一颗石头，不能移动则输，求所有$2^{m}$个边的子集中，只保留这个子集先手必胜的方案个数

2 1
1 2

1

3 3
1 2
1 3
2 3

6

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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