Anik got a directed acyclic graph with some weird properties. For Every node of that graph and where means in-degree of vertex and means out-degree of vertex .
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.
First line contains two integers and (, ): the number of nodes and edges.
Each next m lines contains two integers and (), meaning there is an edge from to .
It is guaranteed that the graph is acyclic and and .
Print the number of different topological sorts of that graph modulo 1000000007 ().
Input | Output |
---|---|
4 2 1 2 2 3 | 4 |
Input | Output |
---|---|
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.