AT_agc016_f [AGC016F] Games on DAG

[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/A

N/A

### 制約 - $ 2\