Limits 1s, 512 MB

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

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 nn and mm (1n1051 ≤ n ≤ 10^5, 0m1050 ≤ m ≤ 10^5): the number of nodes and edges.

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

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

Output

Print the number of different topological sorts of that graph modulo 1000000007 (109+710^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.

Submit

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.