Games on DAG

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$ [samples]