Un corredor compartido

Una ciudad se representa mediante una cuadrícula rectangular de $h$ filas y $w$ columnas. Las filas se numeran de arriba hacia abajo y las columnas de izquierda a derecha. Cada celda está libre o bloqueada.

Dos mensajeros deben atravesar la ciudad. En un paso, cada mensajero puede moverse a una celda libre adyacente hacia la derecha o hacia abajo.

El primer mensajero comienza en $(1,a)$ y debe terminar en $(c,w)$. El segundo mensajero comienza en $(b,1)$ y debe terminar en $(h,d)$.

Dos rutas se llaman compatibles si sus celdas comunes forman una única parte contigua de ambas rutas que contiene al menos dos celdas. Esta parte común puede incluir giros.

Formalmente, deben existir dos celdas distintas $u$ y $v$ en ambas rutas tales que:

• Antes de la celda $u$, las rutas no tienen celdas en común.

• Desde $u$ hasta $v$, inclusive, los mensajeros visitan exactamente la misma secuencia de celdas.

• Después de la celda $v$, las rutas no tienen celdas en común.

Por lo tanto, encontrarse en una sola celda no es suficiente. Las rutas que se separan y vuelven a encontrarse más adelante tampoco son compatibles.

Halla la cantidad de pares de rutas compatibles módulo 10^9+7. Los mensajeros son distintos: un par determina la ruta del primer mensajero y la ruta del segundo mensajero.