F - Games on DAG

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

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

GM 本の辺集合からある部分集合を選び、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 ≤ N ≤ 15
• 1 ≤ M ≤ N(N-1)/2
• 1 ≤ x_i < y_i ≤ N
• (x_i,\ y_i) はすべて相異なる。

入力

N M
x_1 y_1
x_2 y_2
:
x_M y_M


入力例 1

2 1
1 2


出力例 1

1


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

入力例 2

3 3
1 2
1 3
2 3


出力例 2

6


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

入力例 3

4 2
1 3
2 4


出力例 3

2


入力例 4

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


出力例 4

816


Score : 1600 points

Problem Statement

There is a directed graph G with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i is directed from x_i to y_i. Here, x_i < y_i holds. Also, there are no multiple edges in G.

Consider selecting a subset of the set of the M edges in G, and removing these edges from G to obtain another graph G'. There are 2^M different possible graphs as G'.

Alice and Bob play against each other in the following game played on G'. First, place two pieces on vertices 1 and 2, one on each. Then, starting from Alice, Alice and Bob alternately perform the following operation:

• Select an edge i such that there is a piece placed on vertex x_i, and move the piece to vertex y_i (if there are two pieces on vertex x_i, only move one). The two pieces are allowed to be placed on the same vertex.

The player loses when he/she becomes unable to perform the operation. We assume that both players play optimally.

Among the 2^M different possible graphs as G', how many lead to Alice's victory? Find the count modulo 10^9+7.

Constraints

• 2 ≤ N ≤ 15
• 1 ≤ M ≤ N(N-1)/2
• 1 ≤ x_i < y_i ≤ N
• All (x_i,\ y_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print the number of G' that lead to Alice's victory, modulo 10^9+7.

Sample Input 1

2 1
1 2


Sample Output 1

1


The figure below shows the two possible graphs as G'. A graph marked with ○ leads to Alice's victory, and a graph marked with × leads to Bob's victory.

Sample Input 2

3 3
1 2
1 3
2 3


Sample Output 2

6


The figure below shows the eight possible graphs as G'.

Sample Input 3

4 2
1 3
2 4


Sample Output 3

2


Sample Input 4

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


Sample Output 4

816