Entrevista de Trabajo


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C++, Python, Rust

Descripción

Después de que la compañía empezó a contratar programadores de Halk-E, muchos novatos empezaron a aprender Halk-E e intentaron comenzar a trabajar para la compañía lo que provocó mucho desorden en las oficinas centrales. Debido a esto, la compañía decidió hacer una entrevista de trabajo a todos los aspirantes y quienes logren pasar la entrevista trabajarán para la compañía. ¿Serás capaz de trabajar para esta compañía? La entrevista consiste en el siguiente problema:

Tienes N bolas coloridas en una fila. La bola número i desde la izquierda tiene color c_i y tiene peso w_i.

Puede reorganizar las bolas realizando las siguientes dos operaciones cualquier número de veces, en cualquier orden:

  • Operación 1: Seleccionar dos bolas del mismo color. Si el peso total de estas bolas es a lo sumo X, intercambiar sus posiciones.
  • Operación 2: Seleccionar dos bolas de colores diferentes. Si el peso total de estas bolas es a lo sumo Y, intercambiar sus posiciones.

¿Cuántas secuencias diferentes de colores de bolas se pueden obtener? Encuentre el resultado módulo 10^9+7.

Entrada

La primera línea contiene tres enteros N, X y Y (1 \le N \le 2 \times 10^5, 1 \le X, Y \le 10^9).

Le siguen N líneas, cada una de ellas contiene a c_i, w_i (1 \le c_i \le N, 1 \le w_i \le 10^9), el color y el peso de la bola número i.

Salida

Imprime la cantidad de secuencias diferentes de colores de bolas que se pueden obtener, módulo 10^9+7.

Ejemplos

Entrada 1
4 7 3
3 2
4 3
2 1
4 4
Salida 1
2
  • La secuencia de colores (2, 4, 3, 4) se puede obtener intercambiando las posiciones de la primera y tercera bola mediante la operación 2.
  • También es posible intercambiar las posiciones de la segunda y cuarta bola mediante la operación 1, pero no afecta la secuencia de colores.
Entrada 2
1 1 1
1 1
Salida 2
1
Entrada 3
21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15
Salida 3
129729600

Comments

There are no comments at the moment.