# Weird Graph

BUET CSE Fest 2019 Inter...
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$ and $m$ ($1 ≤ n ≤ 10^5$, $0 ≤ m ≤ 10^5$): the number of nodes and edges.

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

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 ($10^9+7$).

## Samples

InputOutput
4 2
1 2
2 3
4

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

### Statistics

93% Solution Ratio
Alamin_justEarliest, Feb '19
LUMBERJACK_MANFastest, 0.0s
LUMBERJACK_MANLightest, 13 kB
ImaginaryNumberShortest, 963B
Toph uses cookies. By continuing you agree to our Cookie Policy.