[AGC016F] Games on DAG

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

[problemUrl]: https://atcoder.jp/contests/agc016/tasks/agc016_f $ 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 $ で割った余りを出力せよ。

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 $ 通りです。 高橋君が勝つ場合は ○ で、負ける場合は × で表しています。 !\[b250f23c38d0f5ec2204bd714e7c1516.png\](https://atcoder.jp/img/agc016/b250f23c38d0f5ec2204bd714e7c1516.png) ### Sample Explanation 2 $ G' $ は次図の $ 8 $ 通りです。 !\[8192fd32f894f708c5e4a60dcdea9d35.png\](https://atcoder.jp/img/agc016/8192fd32f894f708c5e4a60dcdea9d35.png)