Tablero de Movimientos


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++

Tenemos un tablero de H filas y W columnas. Estás parado en la celda superior izquierda y repetirás la siguiente operación: moverte a la celda a la derecha o a la celda que está debajo hasta llegar a la celda inferior derecha.

Pero no puedes pasar por ninguna de las celdas ubicadas en la intersección de las A últimas filas y las B columnas más a la izquierda (hay A \times B celdas bloqueadas en la parte inferior izquierda).

Encuentre el número de maneras de llegar a la celda inferior derecha, como este número puede ser demasiado grande imprímalo mod 10^9+7

Subtareas:

En todas las subtareas está garantizado que 1 \leq A < H y 1 \leq B < W.

  • Subtarea 1 (8 puntos): 1 \leq H \leq 10, 1 \leq W \leq 10
  • Subtarea 2 (12 puntos): 1 \leq H \leq 2, 1 \leq W \leq 100 000
  • Subtarea 3 (30 puntos): 1 \leq H \leq 1000, 1 \leq W \leq 1000
  • Subtarea 3 (50 puntos): 1 \leq H \leq 100 000, 1 \leq W \leq 100 000

Entrada:

En la primera línea T \leq 20, el número de casos

En cada una de las siguientes T líneas se le darán cuatro enteros H, W, A, B, el número de filas, el número de columnas, el número de últimas filas bloqueadas y el número de columnas a la izquierda bloqueadas respectivamente.

Salida:

Un solo entero, el número de maneras de llegar a la celda inferior derecha mod 10^9 + 7.

Ejemplos:

Entrada 1:
4
2 3 1 1
10 7 3 4
100000 100000 99999 99999
100000 100000 44444 55555
Salida 1:
2
3570
1
738162020

Comments

There are no comments at the moment.