Counting Topological Sorts in a DAG

You are given a directed acyclic graph (DAG) with n vertices and m edges. Your task is to determine the number of distinct topological orderings (linear extensions) of the graph. Two topological orderings are considered different if the order of vertices is different.

Let \(MOD = 10^9+7\). You need to compute the result modulo \(MOD\).

Input Constraints:

• 1 ≤ n ≤ 50 (In practice, the test cases will use small values of n so that your solution can compute the result in reasonable time.)
• Edges are given as pairs \((u, v)\) meaning there is a directed edge from vertex \(u\) to vertex \(v\).

Note: If the graph is disconnected or contains no edges, then any permutation of the vertices is a valid topological ordering.

inputFormat

The first line contains two integers n and m representing the number of vertices and edges respectively. The next m lines each contain two integers u and v which indicate a directed edge from vertex u to vertex v.

outputFormat

Output a single integer, which is the number of distinct topological orderings of the given DAG, taken modulo \(10^9+7\).

## sample

3 2
1 2
2 3

1

</p>