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$.