Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Weird Graph

Limits: 1s, 512 MB

Anik got a Directed Acyclic graph with some weird properties. For Every node v of that graph in(v)≤1 and out(v)≤1 where in(v) means in-degree of vertex v and out(v) means out-degree of vertex v.

Now he is wondering how many different topological sorts of that graph is possible. As he is not smart enough to figure it out, you are asked to help him out.

Input

First line contains two integers n m, Number of nodes and edges,1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5

Each next m lines contains two integers p q (1 ≤ p,q ≤ n), meaning there is an edge from p to q. (1 ≤ p, q ≤ n).

It is guaranteed that the graph is Acyclic and in(v) ≤ 1 and out(v) ≤1.

Output

Print the number of different topological sorts of that graph modulo 1000000007(1e9+7).

Samples

InputOutput
4 2
1 2
2 3
4
4 3
1 2
2 3
3 4
1

In-degree of a node means number of edges incoming to a node.

Out-degree of a node means number of edges outgoing from a node.

Discussion