Inestabilidad P64038

Se tiene un vector de pares distintos de enteros, y se desea ordenarlo en orden creciente según el primer entero de cada par. Por ejemplo, el vector:

(2, 5) (1, 8) (10, -3)

quedaría ordenado así:

(1, 8) (2, 5) (10, -3)

Para ordenar el vector usaremos un algoritmo de ordenación no estable, por lo tanto, puede haber más de una ordenación posible. Por ejemplo, el vector:

(2, 5) (-1, 0) (2, 8)

tiene dos ordenaciones posibles:

(-1, 0) (2, 5) (2, 8)

(-1, 0) (2, 8) (2, 5)

Haz un programa que, dado un vector de enteros, cuente cuántas ordenaciones correctas tiene.

Entrada

Para cada caso empieza con un entero $n \le 100000$, que es el tamaño del vector. A continuación hay $n$ pares de enteros $x_i$ $y_i$ ($1 \le i \le n$). No hay dos pares iguales, es decir: $\forall i, j$ $1 \le i, j \le n$, $i \neq j \Rightarrow x_i \neq x_j \vee y_i \neq y_j$

Salida

Para cada caso, escribe el número de ordenaciones correctas del vector módulo 100000007.