{"problem":{"name":"Games on DAG","description":{"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc016_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc016_f","tags":[],"sample_group":[["2 1\n1 2","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)"],["3 3\n1 2\n1 3\n2 3","6\n\nThe figure below shows the eight possible graphs as $G'$.\n\n![image](https://atcoder.jp/img/agc016/8192fd32f894f708c5e4a60dcdea9d35.png)"],["4 2\n1 3\n2 4","2"],["5 10\n2 4\n3 4\n2 5\n2 3\n1 2\n3 5\n1 3\n1 5\n4 5\n1 4","816"]],"created_at":"2026-03-03 11:01:13"}}