# 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

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

Input | Output |
---|---|

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.

Login to submit