{"raw_statement":[{"iden":"problem statement","content":"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$.\nConsider 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'$.\nAlice 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:\n\n*   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.\n\nThe player loses when he/she becomes unable to perform the operation. We assume that both players play optimally.\nAmong the $2^M$ different possible graphs as $G'$, how many lead to Alice's victory? Find the count modulo $10^9+7$."},{"iden":"constraints","content":"*   $2 ≤ N ≤ 15$\n*   $1 ≤ M ≤ N(N-1)/2$\n*   $1 ≤ x_i < y_i ≤ N$\n*   All $(x_i,\\ y_i)$ are distinct."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$:$\n$x_M$ $y_M$"},{"iden":"sample input 1","content":"2 1\n1 2"},{"iden":"sample output 1","content":"1\n\nThe 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.\n\n![image](https://atcoder.jp/img/agc016/b250f23c38d0f5ec2204bd714e7c1516.png)"},{"iden":"sample input 2","content":"3 3\n1 2\n1 3\n2 3"},{"iden":"sample output 2","content":"6\n\nThe figure below shows the eight possible graphs as $G'$.\n\n![image](https://atcoder.jp/img/agc016/8192fd32f894f708c5e4a60dcdea9d35.png)"},{"iden":"sample input 3","content":"4 2\n1 3\n2 4"},{"iden":"sample output 3","content":"2"},{"iden":"sample input 4","content":"5 10\n2 4\n3 4\n2 5\n2 3\n1 2\n3 5\n1 3\n1 5\n4 5\n1 4"},{"iden":"sample output 4","content":"816"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}