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 ≤ 100000, que es el tamaño del vector. A continuación hay n pares de enteros x_i y_i (1 ≤ i ≤ n). No hay dos pares iguales, es decir: ∀ i, j 1 ≤ i, j ≤ n, i ≠ j ⇒ x_i ≠ x_j ∨ y_i ≠ y_j

Salida

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