Consecutive Queue Arrangements

There are \( n \) students in a class numbered \( 1,2,\dots,n \). They want to line up in a queue. Among them, there are \( m \) pairs of close friends. For the \( i\)-th pair (\(1 \le i \le m\)) given by two integers \( a_i \) and \( b_i \), student \( a_i \) must stand immediately before student \( b_i \) in the queue. Determine the total number of valid arrangements of the queue. Since the answer can be very large, output it modulo \(10^9+7\).

Note: It is guaranteed that every student appears in at most one such pair on the left and at most one such pair on the right. If the constraints lead to a cycle or conflict, then there is no valid arrangement and the answer is 0.

The problem can be reformulated as follows. Consider that any pair of students with the required adjacent order forms a block, and any chain of such consecutive constraints can be merged into a single block. Let the number of blocks be \( k \). Then the answer is \( k! \) where \( k = n - m' \) and \( m' \) is the total number of adjacent constraints in all valid chains. In a valid input, each given constraint contributes exactly one to \( m' \), so we have \( k = n - m \).

The answer is \( (n-m)! \) modulo \( 10^9+7 \).

inputFormat

The first line contains two integers \( n \) and \( m \) \((1 \leq n \leq 10^5,\ 0 \leq m \leq n-1)\) representing the number of students and the number of adjacent constraints respectively.

Each of the following \( m \) lines contains two integers \( a_i \) and \( b_i \) \((1 \leq a_i,b_i \leq n)\) indicating that student \( a_i \) must stand immediately before student \( b_i \) in the queue.

outputFormat

Output a single integer: the number of valid queue arrangements modulo \( 10^9+7 \). If the constraints are inconsistent (e.g. form a cycle or conflict), output 0.

sample

3 1
1 2

2